Chapter 6. Computational Geometry
Computational geometry is a field of mathematics that seeks the development of efficient algorithms to solve problems described in terms of basic geometrical objects. We differentiate between combinatorial computational geometry and numerical computational geometry.
Combinatorial computational geometry deals with the interaction of basic geometrical objects—points, segments, lines, polygons, and polyhedra. In this setting, we have three categories of problems:
- Static problems: The construction of a known target object is required from a set of input geometric objects
- Geometric query problems: Given a set of known objects (the search space) and a sought property (the query), these problems deal with the search of objects that satisfy the query
- Dynamic problems: This is similar to the problems from the previous two categories, with the added challenge that the input is not known in advance, and objects are inserted or deleted between queries...
