Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function
作者： Minati De , Gill Barequet
DOI: 10.1007/978-3-319-53007-9_3
关键词:
摘要: The concept of convex polygon-offset distance function was introduced in 2001 by Barequet, Dickerson, and Goodrich. Using this notion point-to-point distance, they showed how to compute the corresponding nearest- farthest-site Voronoi diagram for a set points. In paper we generalize be from point any object with respect an m-sided polygon, study diagrams sets line segments polygons. We show that combinatorial complexity nearest-site n disjoint is O(nm), which asymptotically equal sites same function. addition, result polygonal sites. sites, each having at most k sides, \(O(n(m+k))\). Finally, tree-like structure complexity.
springer.com
core.ac.uk 
sci-hub.se 参考文章(17)
Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, Maksym Zavershynskyi, On the complexity of higher order abstract Voronoi diagrams Computational Geometry: Theory and Applications. ,vol. 48, pp. 539- 551 ,(2015) , 10.1016/J.COMGEO.2015.04.008
Rolf Klein, Concrete and Abstract Voronoi Diagrams ,(1989)
John L. Kelley, Kenneth R. Lucas, W. F. Donoghue, Wendy Robertson, Isaac Namioka, Kennan T. Smith, Ebbe Thue Poulsen, B. J. Pettis, G. Baley Price, W. R. Scott, Linear Topological Spaces ,(1963)
Franz Aurenhammer, Der-Tsai Lee, Rolf Klein, Voronoi Diagrams and Delaunay Triangulations ,(2013)
Rolf Klein, Derick Wood, Voronoi Diagrams Based on General Metrics in the Plane symposium on theoretical aspects of computer science. pp. 281- 291 ,(1988) , 10.1007/BFB0035852
Daniel Leven, Micha Sharir, Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams ,(2011)
L. Paul Chew, Robert L. (Scot) Dyrsdale, Voronoi diagrams based on convex distance functions symposium on computational geometry. pp. 235- 244 ,(1985) , 10.1145/323233.323264
M. McAllister, D. Kirkpatrick, J. Snoeyink, A compact piecewise-linear voronoi diagram for convex sites in the plane Discrete and Computational Geometry. ,vol. 15, pp. 73- 105 ,(1996) , 10.1007/BF02716580
Chee K. Yap, AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments Discrete & Computational Geometry. ,vol. 2, pp. 365- 393 ,(1987) , 10.1007/BF02187890
G. Barequet, M. T. Dickerson, M. T. Goodrich, Voronoi diagrams for convex polygon-offset distance functions Discrete and Computational Geometry. ,vol. 25, pp. 271- 291 ,(2001) , 10.1007/S004540010081