https://scholars.lib.ntu.edu.tw/handle/123456789/624650
標題: | Forest-like abstract: Voronoi diagrams in linear time | 作者: | Bohler C Klein R CHIH-HUNG LIU |
公開日期: | 2014 | 起(迄)頁: | 133-141 | 來源出版物: | 26th Canadian Conference on Computational Geometry, CCCG 2014 | 摘要: | Voronoi diagrams are a well-studied data structure of proximity information, and although most cases require Ω(n log n) construction time, it is interesting and useful to develop linear-time algorithms for certain Voronoi diagrams. For example, the Voronoi diagram of points in convex position, and the medial axis and constrained Voronoi diagram of a simple polygon are a tree or forest structure and can be computed in linear time. In order to provide a more general approach, we study abstract Voronoi diagrams in a domain where each site has a unique face touching the boundary of the domain, implying that the diagram is a forest-like structure, and develop a linear-time algorithm. Since abstract Voronoi diagrams are a category of Voronoi diagrams, our algorithm works for many concrete Voronoi diagrams. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84926044786&partnerID=40&md5=7b456e92860e475ce832e17eecad1e44 https://scholars.lib.ntu.edu.tw/handle/123456789/624650 |
SDG/關鍵字: | Clustering algorithms; Computational geometry; Forestry; Geometry; Constrained Voronoi diagrams; Construction time; Forest structure; Linear time; Linear-time algorithms; Medial axis; Simple polygon; Voronoi diagrams; Graphic methods; Algorithms; Forests; Information Retrieval |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。