On the complexity of higher order abstract Voronoi diagrams

作者: Cecilia Bohler , Panagiotis Cheilaris , Rolf Klein , Chih-Hung Liu , Evanthia Papadopoulou

DOI: 10.1016/J.COMGEO.2015.04.008

关键词:

摘要: Abstract Voronoi diagrams (AVDs) are based on bisecting curves enjoying simple combinatorial properties, rather than the geometric notions of sites and circles. They serve as a unifying concept. Once bisector system any concrete type diagram is shown to fulfill AVD structural results efficient algorithms become available without further effort. In order-k diagram, all points placed into same region that have k nearest neighbors among given sites. This paper first study abstract arbitrary order k. We prove their complexity in plane upper bounded by 2 ( n − ) . So far, an O bound has been only for point Euclidean L p planes, and, recently, line segments, metric. These proofs made extensive use geometry Our result AVDs implies wide range cases which trivial bounds were previously known, slightly sharper known cases. Also, our proof shows reasons this properties certain permutation sequences.

参考文章(23)
Chih-Hung Liu, Evanthia Papadopoulou, D. T. Lee, An output-sensitive approach for the L 1 /L ∞ k-nearest-neighbor Voronoi diagram european symposium on algorithms. pp. 70- 81 ,(2011) , 10.1007/978-3-642-23719-5_7
Jean-Daniel Boissonnat, Camille Wormser, Mariette Yvinec, Curved Voronoi diagrams Springer. pp. 67- 116 ,(2006) , 10.1007/978-3-540-33259-6_2
Franz Aurenhammer, Der-Tsai Lee, Rolf Klein, Voronoi Diagrams and Delaunay Triangulations ,(2013)
Steven Fortune, Voronoi Diagrams and Delaunay Triangulations Handbook of Discrete and Computational Geometry, Second Edition. pp. 377- 388 ,(2004) , 10.1201/9781420035315.CH23
Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, Maksym Zavershynskyi, On the Complexity of Higher Order Abstract Voronoi Diagrams Automata, Languages, and Programming. pp. 208- 219 ,(2013) , 10.1007/978-3-642-39206-1_18
Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure ACM Computing Surveys. ,vol. 23, pp. 345- 405 ,(1991) , 10.1145/116873.116880
Rolf Klein, Kurt Mehlhorn, Stefan Meiser, Randomized incremental construction of abstract Voronoi diagrams Computational Geometry: Theory and Applications. ,vol. 3, pp. 157- 184 ,(1993) , 10.1016/0925-7721(93)90033-3
Evanthia Papadopoulou, Maksym Zavershynskyi, The Higher-Order Voronoi Diagram of Line Segments Algorithmica. ,vol. 74, pp. 415- 439 ,(2016) , 10.1007/S00453-014-9950-0
Noga Alon, E Györi, The number of small semispaces of a finite set of points in the plane Journal of Combinatorial Theory, Series A. ,vol. 41, pp. 154- 157 ,(1986) , 10.1016/0097-3165(86)90122-6