https://scholars.lib.ntu.edu.tw/handle/123456789/624657
標題: | Higher order city Voronoi diagrams | 作者: | Gemsa A Lee D.T Liu C.-H Wagner D. CHIH-HUNG LIU |
公開日期: | 2012 | 卷: | 7357 LNCS | 起(迄)頁: | 59-70 | 來源出版物: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 摘要: | We investigate higher-order Voronoi diagrams in the city metric. This metric is induced by quickest paths in the L 1 metric in the presence of an accelerating transportation network of axis-parallel line segments. For the structural complexity of k th-order city Voronoi diagrams of n point sites, we show an upper bound of O(k(n - k) + kc) and a lower bound of Ω(n + kc), where c is the complexity of the transportation network. This is quite different from the bound O(k(n - k)) in the Euclidean metric [12]. For the special case where k = n - 1 the complexity in the Euclidean metric is O(n), while that in the city metric is Θ(nc). Furthermore, we develop an O(k 2(n + c)log(n + c))-time iterative algorithm to compute the k th-order city Voronoi diagram and an O(nclog 2(n + c)logn)-time divide-and-conquer algorithm to compute the farthest-site city Voronoi diagram. © 2012 Springer-Verlag. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84863099130&doi=10.1007%2f978-3-642-31155-0_6&partnerID=40&md5=6602d7a4427139b3c95d55fe18a67774 https://scholars.lib.ntu.edu.tw/handle/123456789/624657 |
ISSN: | 03029743 | DOI: | 10.1007/978-3-642-31155-0_6 | SDG/關鍵字: | Divide-and-conquer algorithm; Euclidean metrics; Higher order; Higher-order Voronoi diagrams; Iterative algorithm; Line segment; Lower bounds; Structural complexity; Transportation network; Upper Bound; Voronoi diagrams; Algorithms; Computational geometry; Graphic methods |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。