An Efficient Convex Hull Algorithm for Finite Point Sets in 3D Based on the Method of Orienting Curves
An, P. T. ; Trang, L. H.
Optimization: A Journal of Mathematical Programming and Operations Research, 62(7) (2013), 975-988
http://dx.doi.org/10.1080/02331934.2011.623163
This article describes an efficient convex hull algorithm for finite point sets in 3D based on the idea of the Method of Orienting Curves (introduced by Phu in Optimization, 18 (1987) pp. 65–81, for solving optimal control problems with state constraints). The actual run times of our algorithm and known gift-wrapping algorithm on the set of random points (in uniform distribution) show that our algorithm runs significantly faster than the gift-wrapping one.
|
