Document Type : Research Paper

Authors

• Mohammad Heydari ¹
• Ashkan Khalifeh ²

¹ Department of Computer Science, Khansar Campus, University of Isfahan, Iran

² Department of Mathematical and Physical Sciences, College of Arts and Sciences, University of Nizwa, Nizwa 616, Sultanate of Oman

Abstract

Computing the convex hull of a set of points is a fundamental problem in computer science that has applications in various scientific and engineering domains. This paper presents a preprocessing algorithm, named Tiling, that can be utilized before any desired algorithm for computing the convex hull of a set of $n$ points randomly distributed in $\mathbb{R}^3$ by uniform distribution. The key contributions of this work are threefold. First, we provide a complete preprocessing algorithm with detailed implementation. Second, we present rigorous experimental validation showing $2-2.6\times$ performance improvements over the widely used Qhull implementation when applied to uniformly distributed point sets in space. Third, our algorithm demonstrates the ability to eliminate approximately $95-97\%$ of input points while maintaining convex hull correctness, significantly reducing the computational burden for subsequent hull computation.

Keywords

• Convex hull
• Algorithm
• Computational geometry
• Uniform distribution
• Data Preprocessing