EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

A Theoretical Framework for Computing Generalized Weighted Voronoi Diagrams Based on Lower Envelopes

Martin Held, Stefan de Lorenzo

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).

AbstractBibliografiske oplysningerCiteRelated studies

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}
}
Start for free →