Computational Geometry—A Survey
Lee, Preparata · IEEE Transactions on Computers · 1984
We survey the state of the art of computational geometry, a discipline that deals with the complexity of geometric problems within the framework of the analysis of algorithms. This newly emerged area of activities has found numerous applications in various other disciplines, such as computer-aided design, computer graphics, operations research, pattern recognition, robotics, and statistics. Five major problem areas—convex hulls, intersections, searching, proximity, and combinatorial optimizations—are discussed. Seven algorithmic techniques—incremental construction, plane-sweep, locus, divide-and-conquer, geometric transformation, prune-and-search, and dynamization—are each illustrated with an example. A collection of problem transformations to establish lower bounds for geo-metric problems in the algebraic computation/decision model is also included.
Cited by 283 works. doi:10.1109/tc.1984.1676388
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The Design and Analysis of Computer Algorithms
- Linear Programming and Extensions
- Clustering Algorithms
- Principles of Interactive Computer Graphics
- Multidimensional binary search trees used for associative searching
- An Algorithm for Finding Best Matches in Logarithmic Expected Time
- Pattern Classification and Scene Analysis.
- A Characterization of Ten Hidden-Surface Algorithms
- An algorithm for planning collision-free paths among polyhedral obstacles