https://scholars.lib.ntu.edu.tw/handle/123456789/624641
標題: | Minimizing the Diameter of a Spanning Tree for Imprecise Points | 作者: | Liu C.-H Montanari S. CHIH-HUNG LIU |
關鍵字: | Computational geometry; Imprecise data; Minimum diameter spanning trees; Voronoi diagrams | 公開日期: | 2018 | 卷: | 80 | 期: | 2 | 起(迄)頁: | 801-826 | 來源出版物: | Algorithmica | 摘要: | We study the diameter of a spanning tree, i.e., the length of its longest simple path, under the imprecise points model, in which each point is assigned its own occurrence region instead of an exact location. We prove that the minimum diameter of a spanning tree of n points each of which is selected from its respective disk (or axis-parallel square) is polynomial-time computable, contrasting with the fact that minimizing the cost of a spanning tree, i.e. the sum of its edge lengths, for imprecise points is known to be NP-hard. This difference is very interesting since for exact points minimizing the cost seems faster than minimizing the diameter [O(nlog n) versus almost cubic running time]. As the first work regarding the minimum diameter of a spanning tree for imprecise points, our main objective is to investigate essential properties that distinguish the problem from NP-hard instead of minimizing the running time [O(n9) for general disks or O(n6) for unit ones]. Our algorithm mainly utilizes farthest-site Voronoi diagrams for disks and axis-parallel squares, and these diagrams would have their own merits. © 2017, Springer Science+Business Media New York. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85013648316&doi=10.1007%2fs00453-017-0292-6&partnerID=40&md5=595cbf5f2641714747badc30da71df48 https://scholars.lib.ntu.edu.tw/handle/123456789/624641 |
ISSN: | 01784617 | DOI: | 10.1007/s00453-017-0292-6 | SDG/關鍵字: | Graphic methods; Polynomial approximation; Edge length; Imprecise data; Minimum diameter spanning tree; Minimum diameters; Polynomial-time; Running time; Spanning tree; Voronoi diagrams; Computational geometry |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。