TY - GEN
T1 - Improved algorithms for farthest colored Voronoi diagram of segments
AU - Zhu, Yongding
AU - Xu, Jinhui
PY - 2011
Y1 - 2011
N2 - Given n line segments in the plane with each colored by one of k colors, the Farthest Colored Voronoi Diagram (FCVD) is a subdivision of the plane such that the region of a c-colored site (segment or subsegment) s contains all points of the plane for which c is the farthest color and s is the nearest c-colored site. FCVD is a generalization of the Farthest Voronoi Diagram (i.e., k = n) and the regular Voronoi Diagram (i.e., k = 1). In this paper, we first present a simple algorithm to solve the general FCVD problem in an output-sensitive fashion in O((kn + I)α(H)logn) time, where I is the number of intersections of the input and H is the complexity of the FCVD. We then focus on a special case, called Farthest-polygon Voronoi Diagram (FPVD), in which all colored segments form k disjoint polygonal structures (i.e., simple polygonal curves or polygons) with each consisting of segments with the same color. For FPVD, we present an improved algorithm with a running time of O(nlog2n). Our algorithm has better performance and is simpler than the best previously known O(nlog3 n)-time algorithm.
AB - Given n line segments in the plane with each colored by one of k colors, the Farthest Colored Voronoi Diagram (FCVD) is a subdivision of the plane such that the region of a c-colored site (segment or subsegment) s contains all points of the plane for which c is the farthest color and s is the nearest c-colored site. FCVD is a generalization of the Farthest Voronoi Diagram (i.e., k = n) and the regular Voronoi Diagram (i.e., k = 1). In this paper, we first present a simple algorithm to solve the general FCVD problem in an output-sensitive fashion in O((kn + I)α(H)logn) time, where I is the number of intersections of the input and H is the complexity of the FCVD. We then focus on a special case, called Farthest-polygon Voronoi Diagram (FPVD), in which all colored segments form k disjoint polygonal structures (i.e., simple polygonal curves or polygons) with each consisting of segments with the same color. For FPVD, we present an improved algorithm with a running time of O(nlog2n). Our algorithm has better performance and is simpler than the best previously known O(nlog3 n)-time algorithm.
UR - https://www.scopus.com/pages/publications/80051982096
U2 - 10.1007/978-3-642-22616-8_29
DO - 10.1007/978-3-642-22616-8_29
M3 - Conference contribution
SN - 9783642226151
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 372
EP - 386
BT - Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings
T2 - 5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011
Y2 - 4 August 2011 through 6 August 2011
ER -