Advanced Computational Geometry

Sweep line · Voronoi · Delaunay · Duality

1:00

Plane sweep, Voronoi diagrams, Delaunay triangulations, and proximity data structures — the toolkit for answering geometric queries in O(n log n) or better.

By the end, you can

Describe the two data structures that drive a plane sweep and state the role of each.
Explain why Bentley-Ottmann is output-sensitive and state its complexity.
Define a Voronoi diagram and explain why a nearest-neighbor query reduces to point location.
Identify the two event types in Fortune's algorithm and explain what each does.
State the empty-circumcircle property and explain how it connects Voronoi vertices to Delaunay circumcenters.
Explain why Delaunay maximizes the minimum angle and why that matters for mesh generation.
Compare k-d trees, range trees, and Voronoi-based point location for proximity queries.
Name at least three application domains and the specific geometric structure each one uses.

Up next in String Algorithms, Advanced DP & Competitive Techniques