Journal of Convex Analysis 29 (2022), No. 1, 143--156
Copyright Heldermann Verlag 2022
The Lifting Projection of Convex Polyhedra for Finding Delaunay Triangulations
Phan Thanh An
Ho Chi Minh City University of Technology, Ho Chi Minh City, Vietnam, and: Vietnam National University Ho Chi Minh City, Linh Trung Ward,
and: Vietnam National University, Ho Chi Minh City, Vietnam, and: South Ural State University, Chelyabinsk, Russia
thanhan@hcmut.edu.vn
Nam Dung Hoang
University of Science, Vietnam National University, Thanh Xuan, Hanoi, Vietnam
hoangnamdung@hus.edu.vn
Nguyen Kieu Linh
Posts and Telecommunications Institute of Technology, Nguyen Trai, Hanoi, Vietnam
linhnk@ptit.edu.vn
D. Walkup and R. J-B Wets's lifting projection of convex polyhedra in 1969 is used for finding the Delaunay triangulation of a finite planar point set. In concrete, the finite planar point set is lifted on the surface of a paraboloid in R3 with center outside the convex hull of the set. To find quickly the lower convex hull of these points on the paraboloid a restricted region is proposed, thereby eliminating a large number of points to be calculated. The numerical experiments also show that our new version algorithm significantly reduces the running time.
Keywords: Computing science, convex hull, Delaunay triangulation, extreme edge, gift-wrapping algorithm, lifting projection, lower convex hull, pattern recognition, restricted region, Voronoi diagram.
MSC: 52A15, 52B55; 52A30, 52B10, 68U05.
[ Fulltext-pdf (565 KB)] for subscribers only.