Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function

详细信息    查看全文

• 关键词：Polygon ; offset distance function ; Nearest ; site Voroni diagram ; Farthest ; site Voroni diagram ; Convex polygonal sites ; Line segments
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10156
• 期：1
• 页码：24-36
• 丛书名：Algorithms and Discrete Applied Mathematics
• ISBN：978-3-319-53007-9
• 卷排序：10156

文摘

The concept of convex polygon-offset distance function was introduced in 2001 by Barequet, Dickerson, and Goodrich. Using this notion of point-to-point distance, they showed how to compute the corresponding nearest- and farthest-site Voronoi diagram for a set of points. In this paper we generalize the polygon-offset distance function to be from a point to any convex object with respect to an m-sided convex polygon, and study the nearest- and farthest-site Voronoi diagrams for sets of line segments and convex polygons. We show that the combinatorial complexity of the nearest-site Voronoi diagram of n disjoint line segments is O(nm), which is asymptotically equal to that of the Voronoi diagram of n point sites with respect to the same distance function. In addition, we generalize this result to the Voronoi diagram of disjoint convex polygonal sites. We show that the combinatorial complexity of the nearest-site Voronoi diagram of n convex polygonal sites, each having at most k sides, is \(O(n(m+k))\). Finally, we show that the corresponding farthest-site Voronoi diagram is a tree-like structure with the same combinatorial complexity.