Constructing Regular Triangulation via Local Transformations: Theoretical and Practical Advances
COM2 Level 4
Executive Classroom, COM2-04-02
Abstract:
This thesis studies transformation between geometric structures via geometric operations that act on some simplices of a geometric structure. Such a transformation is termed local transformation as an operation utilizes only information local to some neighboring simplices but nothing about other attributes or configurations global in nature to the structure. One famous algorithm of local transformation is Lawson's flip algorithm to construct the Delaunay triangulation from an arbitrary 2D triangulation. Local transformation is simple to be implemented in practice and has been shown to be powerful and efficient to transform among various important fundamental geometric structures. Such a transformation is also useful to repair geometric structures due to small adjustment to their simplices. For today's many-core architecture such as that of the GPU, local transformation is particularly attractive if it can be executed in parallel to gain good speedup at a low cost.
Besides Lawson's flip algorithm, this thesis investigates Shewchuk's star splaying algorithm, and presents the flip-flop algorithm and the twist algorithm in relation to constructing convex hull and regular triangulation, two structures that are geometrically related to Delaunay triangulation.
The thesis starts with a simple and yet non-trivial problem: 2D convex hull. We design a parallel version of the famous Graham's scan, re-casting its scanning stage as a series of flip operations from a star-shaped polygon to the resulting convex hull. In order to avoid the numerical inexactness in constructing star-shaped polygon of the original Graham's scan, we construct the upper and the lower half of the convex hull separately from two star-shaped chains. Such a novel approach is easily realized with the GPU to gain more than 40 times speedup over well-known convex hull implementations.
Next, the thesis examines local transformation to compute Delaunay triangulation, and its generalization of regular triangulation. It is known that one can incrementally construct such triangulation using flips by adding one vertex at a time. That approach, however, strictly alternates between one operation of inserting a vertex and a series of flips to regular triangulation. This dependency of operations limits its use in parallel computation. We discover a novel flip algorithm called flip-flop without such deficiency. This algorithm allows non-restrictive insertion of many vertices into an arbitrary 2D triangulation before transforming it to the regular triangulation. This can also be used to construct the convex hull from a 3D star-shaped polyhedron. Such an approach implemented on the GPU has up to 50 times speedup over existing CPU algorithms.
The thesis continues with examining star splaying, another local transformation that is used to repair convex hull. We propose the gHull algorithm that uses star splaying to construct the 3D convex hull of a point set, and evaluate it against the flip-flop algorithm. It is noted that star splaying is more efficient when its input is close to the convex hull. Along this line, we exploit the relation between Voronoi diagram and convex hull to build an approximation from the restricted digital Voronoi diagram before employing star splaying. As a result, gHull runs very well on the GPU with up to 30 times faster than the best CPU implementation. However, gHull still does not perform as well as flip-flop especially for points in non-uniform distributions.
Understanding from the above studies, we note that star-shaped polytope plays an important role as the only legitimate input for flipping to 2D and 3D convex hull. The thesis then investigates the possibility of obtaining a star-shape polytope from an arbitrary, possibly self-intersecting, one through local transformation. Towards this end, in the 2D setting, we design a novel twist algorithm to transform an arbitrary polygon to a star-shaped one w.r.t.~any chosen point inside its convex hull. In the 3D setting, we discover that a series of flip and twist operations can reach the goal for the special case of a polyhedron that has an extreme vertex connecting to all the other vertices. As for general polyhedrons, the problem remains open.
Excited by the discovery of flip-flop, one wonders what other compromises to the traditional flip algorithm, which is hill-climbing in nature, are possible to compute regular triangulation and convex hull in higher dimensions. The thesis tackles this question by investigating the local transformation from one regular triangulation to another of the same point set in arbitrary dimensions. We discover interesting ways to characterize flipping when the triangulation is cast into a time line. These might be useful to solve the open problem of finding a flip algorithm, free of restrictively sequential execution order, to derive from one regular triangulation to another.