Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
415250 | Computational Geometry | 2014 | 10 Pages |
Abstract
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
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sang Won Bae,