An approximate algorithm for computing multidimensional convex hulls

摘要

To find a convex hull for n points in d-dimensional space, the optimal algorithm has time complexity O(n[d2]). When n and d are large, the execution time is very long. In this paper, we propose an approximate algorithm for computing multidimensional convex hulls. This algorithm finds quasi-two-side approximation to the hull to reduce the time for computing the exact hull boundary. To yield an ε-approximate convex hull, it has time complexity O(ε−1(d−1)n) and storage complexity O(ε−1(d−1)). The approximate algorithm has several advantages: (1) it can easily be implemented, (2) it is suitable for parallel implementation, (3) it is much faster than the exact algorithm, (4) the user can choose to get more accurate results using longer computation time, and (5) it can be applied to solve many problems related to convex hull computation.