Next: Divide and Conquer Up: advalect3 Previous: advalect3
Computational geometry has evolved from the classical discipline of the design and analysis of algorithms. It is concerned with computational complexity of geometric problems that arise in disciplines like, pattern recognition, computer graphics, computer vision, robotics, and very-large scale integrated (VLSI) layout, operation research, statistics, etc. In contrast to the classical approach to proving mathematical theorems about geometry-related problems, this discipline emphasizes the computational aspect of these problem and attempts to exploit the underlying geometric properties, e.g., the metric space, to derive efficient algorithmic solutions. The classes of problems that we address in this chapter include proximity, intersection, searching, point location, convex set, convex hull, Voronoi diagrams, CAD/CAM, etc.