Preconditioning 2D Integer Data for Fast Convex Hull Computations.

Area of Science:

• Computational Geometry
• Computer Science Algorithms

Background:

• Convex hull computation is crucial for many geometric problems.
• Existing methods can be computationally intensive for large datasets.
• Heuristic procedures are often used to reduce point sets before hull computation.

Purpose of the Study:

• To present a novel algorithm for preconditioning 2D data before convex hull construction.
• To demonstrate the efficiency and advantages of the proposed preconditioning method.
• To empirically evaluate the speedup achieved by this approach.

Main Methods:

• Developed a preconditioning algorithm for 2D integer coordinate data within a bounded box.
• Proved the algorithm's execution time complexity is O(n) under the condition min(p, q) ≤ n.
• Designed the preconditioned output as a simple polygonal chain for direct use in O(n) convex hull algorithms.

Main Results:

• The preconditioning algorithm requires no explicit data sorting.
• The reduced point set is directly usable by subsequent O(n) convex hull algorithms.
• Empirical evaluations show a consistent speedup factor of at least four when min(p, q) ≤ n.
• Greater speedup is observed as the ratio min(p, q)/n decreases.

Conclusions:

• The proposed preconditioning algorithm effectively accelerates 2D convex hull computation.
• The method offers significant performance gains, especially for datasets where the bounding box is relatively small compared to the number of points.
• This approach provides a practical enhancement for geometric algorithms requiring convex hull construction.