Farthest line segment Voronoi diagrams

F. Aurenhammer, R.L.S.Drysdale, and H. Krasser


The farthest line segment Voronoi diagram shows properties different from both the closest-segment Voronoi diagram and the farthest-point Voronoi diagram. Surprisingly, this structure did not receive attention in the computational geometry literature. We analyze its combinatorial and topological properties and outline an $O(n \log n)$ time construction algorithm that is easy to implement. No restrictions are placed upon the $n$ input line segments; they are allowed to touch or cross.

Reference: F. Aurenhammer, R.L.S.Drysdale, and H. Krasser. Farthest line segment Voronoi diagrams. Information Processing Letters, 100:220-225, 2006.