作者: 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.