A Theoretical Framework for Computing Generalized Weighted Voronoi Diagrams Based on Lower Envelopes
Geometry · 2025
DOI: 10.3390/geometry2020005 ↗Kurz gefasst
Fachartikel in der Zeitschrift Geometry, 2025. Verfasst von Martin Held und 1 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: the Austrian Science Fund (FWF).
Abstract (Originalsprache)
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.
Förderung
- the Austrian Science Fund (FWF)
Zitieren
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