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

Area of Science:

• Computational Geometry
• Algorithms

Background:

• Convex hull computation on large datasets often requires pre-processing for efficiency.
• Existing methods may not be suitable for streaming data or preserving exact hull properties.

Purpose of the Study:

• To develop a streaming, certificate-based geometric reduction method for large planar point sets.
• To ensure the reduction preserves the exact convex hull while minimizing input size.

Main Methods:

• A novel streaming algorithm based on invariants from incremental convex hull maintenance.
• A certificate-based reduction strategy that identifies and discards interior points.
• Single-pass processing with only local geometric operations.

Main Results:

• The reduction method preserves the exact convex hull of the point set.
• Demonstrated substantial data reduction on both synthetic and real-world datasets.
• Retained 5-11% of points for synthetic data and <1% for real-world data on average.

Conclusions:

• The proposed streaming reduction is effective for large-scale convex hull problems.
• Offers significant efficiency gains by minimizing data input for hull computation.
• Applicable to scenarios with ordered data arrival and large datasets.