Improved algorithms for the farthest colored Voronoi diagram of segments

摘要

Given n line segments in a 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. The 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) log n) 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 the 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 the FPVD, we present an improved algorithm with a running time of O(n log~2 n). Our algorithm has better performance and is simpler than the best previously known O(n log~3 n)-time algorithm.