The L_infinity (L_1) Farthest Line-Segment Voronoi Diagram

We present structural properties of the farthest line-segment Voronoi diagram in the piecewise linear L_∞ and L₁ metrics, which are computationally simpler than the standard Euclidean distance and very well suited for VLSI applications. We introduce the farthest line-segment hull, a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and is related to it similarly to the way an ordinary convex hull relates to the farthest-point Voronoi diagram. In L_∞ (resp. L₁) the farthest line-segment hull, and thus the farthest line-segment Voronoi diagram, has size O(h), where h ranges from O(1) e.g., axis parallel line-segments, to O(n), and it can be constructed in time O(n log h). Once the L_∞ (resp. L₁) farthest line-segment hull is available, the corresponding Voronoi diagram can be constructed in additional O(h) time.