A streaming, certificate-based reduction for convex hull preservation in planar point sets
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).
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}
}
EUVIMED