The Lifting Projection of Convex Polyhedra for Finding Delaunay Triangulations

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.