Sweep-Line Algorithm for Voronoi Diagrams

Explore an advanced algorithm for computing Voronoi diagrams of points and non-intersecting segments in the plane through this conference talk. Learn how the speakers extend Fortune's plane sweep algorithm to handle line segments while maintaining optimal O(n log n) time complexity. Discover applications of this algorithm in VLSI CAD and manufacturing CAM, including its ability to produce the medial axis of polygons. Gain insights into approaches for ensuring numerical robustness without sacrificing efficiency, and understand how the algorithm provides reliably correct results for integer coordinate inputs using robust predicates with lazy-exact arithmetic. Delve into the intricacies of computational geometry and algorithm design in this informative presentation from CppNow.

Simonson, Sydorchuk: Sweep-Line Algorithm for Voronoi Diagrams