Forest-like abstract: Voronoi diagrams in linear time
Journal
26th Canadian Conference on Computational Geometry, CCCG 2014
Pages
133-141
Date Issued
2014
Author(s)
Abstract
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.
Other Subjects
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
Type
conference paper