Bohler CKlein RCHIH-HUNG LIU2022-11-112022-11-112014https://www.scopus.com/inward/record.uri?eid=2-s2.0-84926044786&partnerID=40&md5=7b456e92860e475ce832e17eecad1e44https://scholars.lib.ntu.edu.tw/handle/123456789/624650Voronoi 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.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 Retrievalconference paper2-s2.0-84926044786