https://scholars.lib.ntu.edu.tw/handle/123456789/624655
標題: | Higher-order geodesic Voronoi diagrams in a polygonal domain with holes | 作者: | Liu C.-H Lee D.T. CHIH-HUNG LIU |
公開日期: | 2013 | 起(迄)頁: | 1633-1645 | 來源出版物: | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms | 摘要: | We investigate the higher-order Voronoi diagrams of n point sites with respect to the geodesic distance in a simple polygon with h > 0 polygonal holes and c corners. Given a set of n point sites, the kth-order Voronoi diagram partitions the plane into several regions such that all points in a region share the same k nearest sites. The nearest-site (first-order) geodesic Voronoi diagram has already been well-studied, and its total complexity is O(n+c). On the other hand, Bae and Chwa [3] recently proved that the total complexity of the farthest-site ((n - 1)st-order) geodesic Voronoi diagram and the number of faces in the diagram are Θ(nc) and Θ(nh), respectively. It is of high interest to know what happens between the first-order and the (n - 1)st-order geodesic Voronoi diagrams. In this paper we prove that the total complexity of the kth-order geodesic Voronoi diagram is Θ(k(n - k) + kc), and the number of faces in the diagram is Θ(k(n - k) + kh). Our results successfully explain the variation from the nearest-site to the farthest-site geodesic Voronoi diagrams, i.e., from k = 1 to k = n - 1, and also illustrate the formation of a disconnected Voronoi region, which does not occur in many commonly used distance metrics, such as the Euclidean, L1, and city metrics. We show that the kth-order geodesic Voronoi diagram can be computed in O(k 2(n+c) log(n+c)) time using an iterative algorithm. Copyright © SIAM. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84876047957&doi=10.1137%2f1.9781611973105.117&partnerID=40&md5=751bcf471816537a4bd78f8bd4713f74 https://scholars.lib.ntu.edu.tw/handle/123456789/624655 |
DOI: | 10.1137/1.9781611973105.117 | SDG/關鍵字: | Computational geometry; Geodesy; Iterative methods; Distance metrics; Geodesic distances; Geodesic voronoi diagram; Higher-order Voronoi diagrams; Iterative algorithm; Polygonal domain; Voronoi diagrams; Voronoi regions; Graphic methods |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。