Simonson, Sydorchuk: Sweep-Line Algorithm for Voronoi Diagrams

We present an algorithm for computing the Voronoi diagram of input data sets of points and non-intersecting segments in the plane. Building upon the plane sweep algorithm by Fortune that computes the Voronoi diagram of points we extend the algorithm to line segments while maintaining optimal O(n log n) time complexity. The Voronoi diagram of line segments can trivially produce the medial axis of polygons and has many applications in VSLI CAD, and manufacturing CAM. Approaches to ensuring numerical robustness without sacrificing efficiency will be discussed. We will show that the algorithm provides reliably correct results for integer coordinate inputs by using robust predicates that rely on lazy-exact arithmetic. --- *--* ---