Determining the convex hull, its lower convex hull, and Voronoi diagram of a point set is a basic operation for many applications of pattern recognition, image processing, and data mining. To date, the lower convex hu...
详细信息
ISBN:
(数字)9783319179964
ISBN:
(纸本)9783319179964;9783319179957
Determining the convex hull, its lower convex hull, and Voronoi diagram of a point set is a basic operation for many applications of pattern recognition, image processing, and data mining. To date, the lower convex hull of a finite point set is determined from the entire convex hull of the set. There arises a question "How can we determine the lower convex hull of a finite point set without relying on the entire convex hull?" In this paper, we show that the lower convex hull is wrapped by lower facets starting from an extreme edge of the lower convex hull. Then a direct method for determining the lower convex hull of a finite point set in 3D without the entire convex hull is presented. The actual running times on the set of random points (in the uniform distribution) show that our corresponding algorithm runs significantly faster than the incremental convex hull algorithm and some versions of the gift-wrapping algorithm.
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 co...
详细信息
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.
暂无评论