لطفا منتظر باشید ...
Chapter notes
This chapter barely scratches the surface of computational-geometry algorithms and techniques. Books on computational geometry include those by Preparata and Shamos [247], Edelsbrunner [83], and O'Rourke [235].Although geometry has been studied since antiquity, the development of algorithms for geometric problems is relatively new. Preparata and Shamos note that Section 33.2, which determines whether any segments intersect, is due to Shamos and Hoey [275].The original version of Graham's scan is given by Graham [130]. The package-wrapping algorithm is due to Jarvis [165]. Using a decision-tree model of computation, Yao [318] proved a lower bound of Ω(n lg n) for the running time of any convex-hull algorithm. When the number of vertices h of the convex hull is taken into account, the prune-and-search algorithm of Kirkpatrick and Seidel [180], which takes O(n lg h) time, is asymptotically optimal.The O(n lg n)-time divide-and-conquer algorithm for finding the closest pair of points is by Shamos and appears in Preparata and Shamos [247]. Preparata and Shamos also show that the algorithm is asymptotically optimal in a decision-tree model.
