A Theoretical Framework for Computing Generalized Weighted Voronoi Diagrams Based on Lower Envelopes
Geometry · 2025
DOI: 10.3390/geometry2020005 ↗At a glance
Journal article in Geometry, 2025. Written by Martin Held and 1 co-authors. 18 references. The full text is freely available (open access, CC BY 4.0). Funded by: the Austrian Science Fund (FWF).
Abstract (original language)
This paper presents a theoretical framework for constructing generalized weighted Voronoi diagrams (GWVDs) of weighted points and straight-line segments (“sites”) in the Euclidean plane, based on lower envelopes constructed in three-dimensional space. Central to our approach is an algebraic distance function that defines the minimum weighted distance from a point to a site. We also introduce a parameterization for the bisectors, ensuring a precise representation of Voronoi edges. The connection to lower envelopes allows us to derive (almost tight) bounds on the combinatorial complexity of a GWVD. We conclude with a short discussion of implementation strategies, ranging from leveraging computational geometry libraries to employing graphics hardware for approximate solutions.
Funding
- the Austrian Science Fund (FWF)
Cite
APA
Held, M., & Lorenzo, S. D. (2025). A Theoretical Framework for Computing Generalized Weighted Voronoi Diagrams Based on Lower Envelopes. Geometry. https://doi.org/10.3390/geometry2020005
Vancouver
Held M, Lorenzo SD. A Theoretical Framework for Computing Generalized Weighted Voronoi Diagrams Based on Lower Envelopes. Geometry. 2025. doi:10.3390/geometry2020005
BibTeX
@article{Held2025,
author = {Held, Martin and Lorenzo, Stefan de},
title = {A Theoretical Framework for Computing Generalized Weighted Voronoi Diagrams Based on Lower Envelopes},
journal = {Geometry},
year = {2025},
doi = {10.3390/geometry2020005}
}
EUVIMED