https://scholars.lib.ntu.edu.tw/handle/123456789/624646
標題: | On the complexity of higher order abstract Voronoi diagrams | 作者: | Bohler C Cheilaris P Klein R Liu C.-H Papadopoulou E Zavershynskyi M. CHIH-HUNG LIU |
關鍵字: | Abstract Voronoi diagrams; Computational geometry; Distance problems; Higher order Voronoi diagrams; Voronoi diagrams | 公開日期: | 2015 | 卷: | 48 | 期: | 8 | 起(迄)頁: | 539-551 | 來源出版物: | Computational Geometry: Theory and Applications | 摘要: | Voronoi diagrams (AVDs) are based on bisecting curves enjoying simple combinatorial properties, rather than on the geometric notions of sites and circles. They serve as a unifying concept. Once the bisector system of any concrete type of Voronoi diagram is shown to fulfill the AVD properties, structural results and efficient algorithms become available without further effort. In a concrete order-k Voronoi diagram, all points are placed into the same region that have the same k nearest neighbors among the given sites. This paper is the first to study abstract Voronoi diagrams of arbitrary order k. We prove that their complexity in the plane is upper bounded by 2k(n - k). So far, an O(k(n - k)) bound has been shown only for point sites in the Euclidean and Lp planes, and, recently, for line segments, in the Lp metric. These proofs made extensive use of the geometry of the sites. Our result on AVDs implies a 2k(n - k) upper bound for a wide range of cases for which only trivial upper complexity bounds were previously known, and a slightly sharper bound for the known cases. Also, our proof shows that the reasons for this bound are combinatorial properties of certain permutation sequences. © 2015 Elsevier B.V. All rights reserved. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84929309050&doi=10.1016%2fj.comgeo.2015.04.008&partnerID=40&md5=5545ccce3b0b322bc8daa14c7817ae91 https://scholars.lib.ntu.edu.tw/handle/123456789/624646 |
ISSN: | 09257721 | DOI: | 10.1016/j.comgeo.2015.04.008 | SDG/關鍵字: | Algorithms; Computational geometry; Concretes; Geometry; Nearest neighbor search; Arbitrary order; Combinatorial properties; Complexity bounds; Distance problems; Higher-order Voronoi diagrams; K-nearest neighbors; Order-k Voronoi diagrams; Voronoi diagrams; Graphic methods |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。