Computational Geometry,Fundamental Structures:Triangulations

Triangulations

In geometric data processing, structures that partition the geometric input, as well as connectivity structures for geometric objects, play an important role. Versatile tools in this context are triangular meshes, often called triangulations. A triangulation of a geometric domain such as a polygon in R2 or a polyhedron in R3 is a partition into simplices that meet only at shared faces. A triangulation of a point set S is a triangulation of the convex hull of S, such that the vertices in the triangulation are exactly the points in S.

In the following sections, we first discuss the most famous of all triangulations, the Delaunay triangulation. We then address triangulations of polygons and polyhedra in R3. Finally we describe a recent generalization of triangulations: the pseudo-triangulation.

Delaunay Triangulation

In this section we provide additional detail on the Delaunay triangulation of a set S = {s1,... , sn} of points in Rd, which was introduced in Section 62.4. There we defined the Delaunay triangulation as the dual of the Voronoi diagram. In the plane, for instance, the Delaunay triangulation has an edge between sites si and sj if and only if the Voronoi cells of si and sj share a boundary edge. In higher dimensions, there is an edge between si and sj if their Voronoi cells share a (d − 1)-facet. The Delaunay triangulation can also be defined directly. If we restrict ourselves for the moment to a set S of points in R2 then the Delaunay triangulation of S, DT (S), is defined by the empty-circle condition: a triangle ∆ defined by three points si, sj , and sk is part of DT (S) if and only if ∆’s circumcircle neither encloses nor passes through any other points of S. More generally, d+ 1 points in Rd define a simplex in the Delaunay triangulation if and only if its circumscribed sphere neither encloses nor passes through any other points of S. If no d + 1 points of S are co-spherical then DT (S) is indeed a triangulation. If d + 2 or more points are co-spherical, then DT (S) can contain cells with more than d + 1 sides. Fortunately, such cells can easily be further decomposed in simplices—with a bottom-vertex triangulation, for example—so such degeneracies are not a real problem. To simplify the description, we from now on assume that these degeneracies do not occur.

In the previous section we have seen a close connection between Voronoi diagrams in Rd and intersections of half-spaces in Rd+1. Similarly, there is a close connection between the Delaunay triangulation in Rd and convex hulls in Rd+1. Let’s again restrict ourselves to the case d = 2. Consider the transformation that maps a site s = (sx, sy ) in R2 onto the point λ(sx, sy ) = (sx, sy , s2 + s2 ) in R3. In other words, s is “lifted” vertically onto the unit paraboloid to obtain λ(s). Let λ(S) be the set of lifted sites. Then if we project the lower convex hull of λ(S)—the part of the convex hull consisting of the facets facing downward—back onto the xy-plane, we get the Delaunay triangulation of S.

The Delaunay triangulation is the “best” triangulation with respect to many optimality criteria. The Delaunay triangulation:

• minimizes the maximum radius of a circumcircle;

• maximizes the minimum angle;

• maximizes the sum of inscribed circle radii;

• minimizes the “potential energy” of a piecewise-linear interpolating surface.

Also, the distance between any two vertices of the Delaunay triangulation along the triangulation edges is at most 2.42 times their Euclidean distance, that is, the dilation of the Delaunay triangulation is 2.42. Finally, the Delaunay triangulation contains as a subgraph many other interesting graphs:

where EM ST is the Euclidean minimum spanning tree, RN G is the relative neighborhood graph, and GG is the Gabriel graph (see [49] for details on these graphs).

Since the Delaunay triangulation is the dual of the Voronoi diagram, any algorithm presented in Section 62.4.2 can by used to efficiently compute the Delaunay triangulation. We therefore refrain from presenting any additional algorithms at this point.

Polygons

Triangulating a simple polygon P is not only an interesting problem in its own right, but it is also an important preprocessing step for many algorithms. For example, many shortest- path and visibility problems on a polygon P can be solved in linear time if a triangulation of P is given [27]. It is fairly easy to show that any polygon can indeed by decomposed into triangles by adding a number of diagonals and, moreover, that the number of triangles in any triangulation of a simple polygon with n vertices is n − 2.

There are many algorithms to compute a triangulation of a simple polygon. Most of them run in O(n log n) time. Whether is is possible to triangulate a polygon in linear time was a prominent open problem for several years until Chazelle [13], after a series of interim results, devised a linear-time algorithm. Unfortunately, his algorithm is more of theoretical than of practical interest, so it is probably advisable to use a deterministic algorithm with O(n log n) running time, such as the one described below, or one of the slightly faster

randomized approaches with a time complexity of O(n log∗ n) [39].

In the remainder of this section we sketch a deterministic algorithm that triangulates a simple polygon P with n vertices in O(n log n) time. We say that a polygon P is monotone with respect to a line £ if the intersection of any line £1 perpendicular to £ with P is connected. A polygon that is monotone with respect to the x-axis is called x-monotone.

Now the basic idea is to decompose P into monotone polygons and then to triangulate each of these monotone polygons in linear time.

There are several methods to decompose a simple polygon into x-monotone polygons in O(n log n) time. One approach is to sweep over P twice, from left to right and then from right to left, and to add appropriate edges to vertices that did not previously have at least one edge extending to the left and at least one edge extending to the right. A more detailed description of this or related approaches can be found in [7, 24].

Triangulating a monotone polygon. Now suppose we are given an x-monotone polygon P —see Fig. 62.9. We consider its vertices p1,..., pn from left to right and use a stack to store the vertices of the not-yet-triangulated part of the polygon (which necessarily form a reflex chain) to the left of our current vertex pi. If pi is adjacent to pi−1, as in see Fig. 62.9(a), then we pop vertices from the stack and connect them to pi until the stack (including pi) forms a reflex chain again. In particular that might mean that we simply add pi to the stack. If pi is adjacent to the leftmost vertex on the stack, which could be pi−1, as in see Fig. 62.9(b), then we connect pi to each vertex of the stack and clear the stack of all vertices except pi and pi−1. This algorithm triangulates P in linear time.

Polyhedra

In this section we briefly discuss triangulations (or tetrahedralizations) of three-dimensional polyhedra. A polyhedron P is a connected solid with a piecewise linear boundary (that is, its boundary is composed of polygons). We assume P to be non-degenerate: A sufficiently small ball around any point of the boundary of P contains a connected component of the interior as well as the exterior of P . The number of vertices, edges, and faces of a non- degenerate tetrahedron are linearly related.

Three dimensions unfortunately do not behave as nicely as two. Two triangulations of the same input data may contain quite different numbers of tetrahedra. For example, a triangulation of a convex polyhedron with n vertices may contain between n − 3 and (n−2) tetrahedra. Furthermore, some non-convex polyhedra can not be triangulated at all without the use of additional (so-called Steiner ) points. The most famous example is Sch¨onhardt’s polyhedron. Finally, it is NP-complete to determine whether a polyhedron can be triangulated without Steiner points and to test whether k Steiner points are sufficient [46]. Chazelle [12] constructed a polyhedron with n vertices that requires Ω(n2) Steiner points. On the other hand, any polyhedron can be triangulated with O(n2) tetrahedra, matching his lower bound. If one pays special attention to the reflex vertices of the input polyhedron P , then it is even possible to triangulate P using only O(n + r2) tetrahedra, where r is the number of reflex edges of P [15].

Pseudo-Triangulations

In recent years a relaxation of triangulations, called pseudo-triangulations, has received considerable attention. Here, faces are bounded by three concave chains, rather than by three line segments. More formally, a pseudo-triangle is a planar polygon that has exactly three convex vertices with internal angles less than π, all other vertices are concave. Note that every triangle is a pseudo-triangle as well. The three convex vertices of a pseudo- triangle are called its corners. Three concave chains, called sides, join the three corners. A pseudo-triangulation for a set S of points in the plane is a partition of the convex hull of S into pseudo-triangles whose vertex set is exactly S—see Fig. 62.8.

Pseudo-triangulations, also

called geodesic triangulations, were originally studied for convex sets and for simple polygons in the plane because of their applications to visibility [40, 41] and ray shooting [16, 25]. But in the last few years they also found application in robot motion planning [55] and kinetic collision detection [1, 35].

Of particular interest are the so-called minimum pseudo-triangulations, which have the minimum number of pseudo-triangular faces among all possible pseudo-triangulations of a given domain. They were introduced by Streinu [55], who established that every mini- mum pseudo-triangulation of a set S of n points consists of exactly n − 2 pseudo-triangles (here we do not count the outer face). Note that such a statement cannot be made for ordinary triangulations: there the number of triangles depends on the number of points that show up on the convex hull of S. Minimum pseudo-triangulations are also referred to as pointed pseudo-triangulations. The name stems from the fact that every vertex v of a minimum pseudo-triangulation has an incident region whose angle at v is greater than π. The converse is also true (and can be easily established via Euler’s relation): If every vertex of a pseudo-triangulation is pointed—it has an incident angle greater than π—then this pseudo-triangulation has exactly n − 2 pseudo-triangles and is therefore minimum. A pseudo-triangulation is called minimal (as opposed to minimum) if the union of any two faces is not a pseudo-triangle. In general, all minimum pseudo-triangulations are also minimal, but the opposite is not necessarily true—see Figure 62.10(a) for an example of a minimal but not minimum pseudo-triangulation.

The great variety of applications in which pseudo-triangulations are successfully employed prompted a growing interest in their geometric and combinatoric properties, which often deviate substantially from those of ordinary triangulations. An example of a nice property of pseudo-triangulations is that every point set in the plane admits a pseudo-triangulation of maximum vertex degree 5 [33]. (This bound is tight.) Again, this is not the case for ordinary triangulations: any ordinary triangulation of the point set depicted in Figure 62.10(b), contains a vertex of degree n − 1.

Up to now there are unfortunately no extensions of pseudo-triangulations to dimensions higher than two which retain a significant subset of their useful planar properties.