Journal of Algorithms and Computation
Open Access

Efficient Preprocessing of 3D Data for Convex Hull Computation

Document Type : Research Paper

Authors

Mohammad Heydari 1
Ashkan Khalifeh 2

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

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

https://doi.org/10.22059/jac.2026.411069.1253
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
Journal of Algorithms and Computation
Volume 57, Issue 2
December 2025
Pages 187-201

Home

Guide for Authors

Submit Manuscript

Reviewers

Contact Us