Chapter 7 a Survey of Computational Geometry

Computational geometry takes an algorithmic approach to the study of geometrical problems. The field of computational geometry has also benefited from its interactions with other disciplines within computer science such as VLSI, database theory, robotics, computer vision, computer graphics, pattern recognition and learning theory. These areas offer a rich variety of problems that are inherently geometrical. This chapter presents a survey for some selected areas of computational geometry, with a strong bias towards problems with an optimization component. The chapter describes five key concepts and fundamental structures that permeate much of computational geometry, and therefore are somewhat essential to a proper understanding of the material. The structures covered are convex hulls, arrangements, geometric duality, Voronoi diagram, and point location data structures. The four popular geometric graphs are described: minimum and maximum spanning trees, relative neighborhood graphs, and Gabriel graphs. The path planning is briefly discussed. The matching and the traveling salesman type problems in computational geometry are also discussed in the chapter. The results on a variety of problems related to shape analysis and pattern recognition is also presented.