AI Insight
This paper presents a streaming algorithm that reduces the number of points in large planar datasets before computing their convex hull, while guaranteeing that the exact convex hull is preserved. The method uses geometric certificates to identify and discard points that are provably interior to the hull, operating in a single pass through the data using only local computations. Experiments on both synthetic and real-world datasets show the approach retains as few as 5 to 11 percent of points on synthetic data and under 1 percent on large real-world datasets, demonstrating significant input size reduction.
Why it matters
Efficient convex hull computation is fundamental to computational geometry applications including robotics, geographic information systems, and computer vision, and this reduction technique could meaningfully lower computational costs when processing large spatial datasets in constrained or streaming environments.
by Oswaldo Cadenas
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.
Source: A streaming, certificate-based reduction for convex hull preservation in planar point sets