Algorithms in a Nutshell, 2nd Edition

Chapter 9. Computational Geometry

Computational geometry is the rigorous application of mathematics to compute geometric structures and their properties accurately and efficiently. We confine our discussion to solve problems involving two-dimensional structures represented in the Cartesian plane; there are natural extensions to n-dimensional structures. Mathematicians have investigated such problems for centuries, but the field has been recognized as a systematic study since the 1970s. This chapter presents the computational abstractions used to solve computational geometry problems. These techniques are by no means limited to geometry problems and have many real-world applications.

Algorithms in this category solve numerous real-world problems:

Convex hull

Compute the smallest convex shape that fully encloses a set of n two-dimensional points, P. This can be solved in O(n log n) instead of an O(n⁴) brute-force solution.

Intersecting line segments

Compute all intersections given a set of n two-dimensional line segments, S. This can be solved in O((n + k) log n) where k is the number of intersections, instead of an O(n²) brute-force solution.

Voronoi diagram

Partition a plane into regions based on distance to a set of n two-dimensional points, P. Each of the n regions consists of the Cartesian points closer to point p_i ∈ P than any other p_j ∈ P. This can be solved in O(n log n).

Along the way we describe the powerful Line Sweep technique that can be used, ultimately, to ...