Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments

We establish a tight bound on the worst-case combinatorial complexity of the farthest-color Voronoi diagram of line segments in the plane. More precisely, given k sets of n   total line segments, the combinatorial complexity of the farthest-color Voronoi diagram is shown to be Θ(kn+h)Θ(kn+h) in the worst case, under any LpLp metric with 1≤p≤∞1≤p≤∞, where h is the number of crossings between the n line segments. We then present an improved analysis on Huttenlocher et al.'s algorithm [9] to show that the diagram can be computed in O((kn+h)logn) time under the L1L1 or L∞L∞ metric, or in O((kn+h)(α(k)logk+logn)) time under the LpLp metric for any 1