Abstract Voronoi Diagrams from Closed Bisecting Curves
Journal
International Journal of Computational Geometry and Applications
Journal Volume
27
Journal Issue
3
Pages
221-240
Date Issued
2017
Author(s)
Abstract
We present the first algorithm for constructing abstract Voronoi diagrams from bisectors that are unbounded or closed Jordan curves. It runs in expected O(s2nlog(max{s,n}) σni=2nm i/i) many steps and O(σni=3nm i) space, where n is the number of sites, mi denotes the average number of faces (connected components) per Voronoi region in any diagram of a subset of i sites, and s is the maximum number of intersection points between any two related bisectors. © 2017 World Scientific Publishing Company.
Subjects
Abstract Voronoi diagrams; closed bisecting curves; computational geometry; distance problems; Voronoi diagrams
Type
journal article