EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A streaming, certificate-based reduction for convex hull preservation in planar point sets

Oswaldo Cadenas iD

PLOS One · 19.05.2026 · 21 (5) · e0349577

DOI: 10.1371/journal.pone.0349577 ↗

Kurz gefasst

Fachartikel in der Zeitschrift PLOS One, online erschienen am 19.05.2026. Verfasst von Oswaldo Cadenas. Beteiligte Einrichtung: School of Computer Science and Digital Technologies, London South Bank University, London, United Kingdom. Die Arbeit nennt 20 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Convex hull computation on large planar point sets is commonly preceded by geometric filtering to reduce input size. Motivated by invariants used in incremental convex hull maintenance, we derive a streaming, certificate-based reduction that discards only points certified interior to the hull. We show that the reduction preserves the exact convex hull and operates in a single streaming pass with only local geometric operations. Experiments on synthetic and real-world datasets demonstrate substantial reduction, retaining between 5% and 11% of input points on average for synthetic distributions and below 1% on large real-world data under typical arrival order.

Autor:innen und Institutionen

  • School of Computer Science and Digital Technologies, London South Bank University, London, United Kingdom.

ORCID-Profile: Oswaldo Cadenas

Zitieren

APA

Cadenas, O. (2026). A streaming, certificate-based reduction for convex hull preservation in planar point sets. PLOS One, 21(5), e0349577. https://doi.org/10.1371/journal.pone.0349577

Vancouver

Cadenas O. A streaming, certificate-based reduction for convex hull preservation in planar point sets. PLOS One. 2026;21(5):e0349577. doi:10.1371/journal.pone.0349577

BibTeX
@article{Cadenas2026,
  author = {Cadenas, Oswaldo},
  title = {A streaming, certificate-based reduction for convex hull preservation in planar point sets},
  journal = {PLOS One},
  year = {2026},
  volume = {21},
  number = {5},
  pages = {e0349577},
  doi = {10.1371/journal.pone.0349577}
}
Kostenlos starten →