EUVIMEDEUVIMED entdecken
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 ↗

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

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →