https://scholars.lib.ntu.edu.tw/handle/123456789/624644
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Bohler C | en_US |
dc.contributor.author | Liu C.-H | en_US |
dc.contributor.author | Papadopoulou E | en_US |
dc.contributor.author | Zavershynskyi M. | en_US |
dc.contributor.author | CHIH-HUNG LIU | en_US |
dc.date.accessioned | 2022-11-11T02:58:58Z | - |
dc.date.available | 2022-11-11T02:58:58Z | - |
dc.date.issued | 2016 | - |
dc.identifier.issn | 09257721 | - |
dc.identifier.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84985906123&doi=10.1016%2fj.comgeo.2016.08.004&partnerID=40&md5=edebfbce8f31961b0df9e43a31c408f5 | - |
dc.identifier.uri | https://scholars.lib.ntu.edu.tw/handle/123456789/624644 | - |
dc.description.abstract | Given a set of n sites in the plane, their order-k Voronoi diagram partitions the plane into regions such that all points within one region have the same k nearest sites. The order-k abstract Voronoi diagram offers a unifying framework that represents a wide range of concrete order-k Voronoi diagrams. It is defined in terms of bisecting curves satisfying some simple combinatorial properties, rather than the geometric notions of sites and distance. In this paper we develop a randomized divide-and-conquer algorithm to compute the order-k abstract Voronoi diagram in expected O(kn1+ε) operations. For solving small sub-instances in the divide-and-conquer process, we also give two auxiliary algorithms with expected O(k2nlogn) and O(n22α(n)logn) time, respectively, where α(⋅) is the inverse of the Ackermann function. Our approach directly implies an O(kn1+ε)-time algorithm for several concrete order-k instances such as points in any convex distance, disjoint line segments or convex polygons of constant size in the Lp norms, and others. It also provides basic techniques that can enable the application of well-known random sampling techniques to the construction of Voronoi diagrams in the abstract setting and for non-point sites. © 2016 Elsevier B.V. | - |
dc.relation.ispartof | Computational Geometry: Theory and Applications | - |
dc.subject | Abstract Voronoi diagram; Divide and conquer; Geometric randomized algorithm; Higher-order Voronoi diagram; k nearest neighbors | - |
dc.subject.other | Algorithms; Computational geometry; Concretes; Nearest neighbor search; Divide and conquer; Higher-order Voronoi diagrams; K-nearest neighbors; Randomized Algorithms; Voronoi diagrams; Graphic methods | - |
dc.title | A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams | en_US |
dc.type | journal article | en |
dc.identifier.doi | 10.1016/j.comgeo.2016.08.004 | - |
dc.identifier.scopus | 2-s2.0-84985906123 | - |
dc.relation.pages | 26-38 | - |
dc.relation.journalvolume | 59 | - |
item.fulltext | no fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
item.cerifentitytype | Publications | - |
item.openairetype | journal article | - |
item.grantfulltext | none | - |
crisitem.author.dept | Electrical Engineering | - |
crisitem.author.orcid | 0000-0001-9683-5982 | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。