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

Oswaldo Cadenas

PLOS ONE, 2026, vol. 21, issue 5, 1-17

Abstract: 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.

Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0349577 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 49577&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0349577

DOI: 10.1371/journal.pone.0349577

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().