https://scholars.lib.ntu.edu.tw/handle/123456789/624651
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:59:01Z | - |
dc.date.available | 2022-11-11T02:59:01Z | - |
dc.date.issued | 2014 | - |
dc.identifier.issn | 03029743 | - |
dc.identifier.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84921648246&doi=10.1007%2f978-3-319-13075-03&partnerID=40&md5=0ee1e52de7b5570adfe9194e280d0fb7 | - |
dc.identifier.uri | https://scholars.lib.ntu.edu.tw/handle/123456789/624651 | - |
dc.description.abstract | Given a set of 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 is defined in terms of bisecting curves satisfying some simple combinatorial properties, rather than the geometric notions of sites and distance, and it represents a wide class of order-k concrete Voronoi diagrams. In this paper we develop a randomized divide-andconquer 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 sub-algorithms with expected O(k2n log n) and O(n22α(n) log n) time, respectively. This directly implies an O(kn1+ε)-time algorithm for several concrete order-k instances such as points in any convex distance, disjoint line segments and convex polygons of constant size in the Lp norm, and others. © Springer International Publishing Switzerland 2014. | - |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | - |
dc.subject | Abstract Voronoi Diagram; Divide and Conquer; Higher-Order Voronoi Diagram; Randomized Algorithm | - |
dc.subject.other | Computational geometry; Concretes; Graphic methods; Combinatorial properties; Divide and conquer; Divide-and-conquer algorithm; Higher-order Voronoi diagrams; Order-k Voronoi diagrams; Randomized Algorithms; Time algorithms; Voronoi diagrams; Algorithms | - |
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.1007/978-3-319-13075-03 | - |
dc.identifier.scopus | 2-s2.0-84921648246 | - |
dc.relation.pages | 27-37 | - |
dc.relation.journalvolume | 8889 | - |
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 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。