https://scholars.lib.ntu.edu.tw/handle/123456789/624639
標題: | Forest-like abstract Voronoi diagrams in linear time | 作者: | Bohler C Klein R Lingas A Liu C.-H. CHIH-HUNG LIU |
關鍵字: | Abstract Voronoi diagrams; Forest structures; General distance; Linear-time algorithms; Voronoi diagrams | 公開日期: | 2018 | 卷: | 68 | 起(迄)頁: | 134-145 | 來源出版物: | Computational Geometry: Theory and Applications | 摘要: | Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. [1] we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V(S) is a tree, and for each subset S′⊂S, a forest with one face per site. If the order of Voronoi regions of V(S) along the boundary of D is given, then V(S) inside D can be constructed in linear time. © 2017 Elsevier B.V. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85023625891&doi=10.1016%2fj.comgeo.2017.06.013&partnerID=40&md5=93e2ea83a3ca71c7b55db1c56684b433 https://scholars.lib.ntu.edu.tw/handle/123456789/624639 |
ISSN: | 09257721 | DOI: | 10.1016/j.comgeo.2017.06.013 | SDG/關鍵字: | Clustering algorithms; Computational geometry; Forestry; Distance measure; Forest structure; General distance; Linear time; Linear-time algorithms; Voronoi diagrams; Voronoi regions; Graphic methods |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。