Polygon triangulation: Efficiency and minimality

(1)

Polygon triangulation: Efficiency and minimality

著者 Asano Takao, Asano Tetsuo, Ypinter Ron

著者別表示浅野哲夫

journal or

publication title

Journal of Algorithms

volume 7

number 2

page range 221‑231

year 1986

URL http://doi.org/10.24517/00062799

doi: 10.1016/0196-6774(86)90005-2

Creative Commons : 表示 ‑ 非営利 ‑ 改変禁止 http://creativecommons.org/licenses/by‑nc‑nd/3.0/deed.ja

(2)

Polygon Triangulation: Efficiency and Minimality

TAKAO ASANO*

Depurtment of Muthemuticul Engineering and Instrumentution Physics, Fuculty of Engineering, University of Tokyo, Bunkyo-ku, Tokyo, I1 3 Japan

TETSUO ASANO+

Depurtment of Electricul Engineering and Computer Sciences, University of Culiforniu, Berkeley, Culiforniu

AND RON Y. ^PINTER

IBM Isruel Scientific Center, Meyer Advanced Technology Center, Technion Cicv, Huifu 32 Ooo, Isruel

Received April 30,1984

In this paper we show that Q( n log n) operations are necessary to triangulate a polygonal region with n vertices which contains holes (or windows). Also, we present a polynomial time algorithm for partitioning a polygonal region which may have a fixed number of holes into a minimum number of triangles. Finally, we discuss arbitrary-as opposed to chordal-minimum-number triangulations. 1,19X6 Academic ,%a\. Inc.

1. INTRODUCTION

In various application domains, the subject of triangulating polygonal regions-simple polygons as well as regions that may enclose polygonal holes (or “ windows”)-has drawn considerable attention. From a computa- tional point of view, there are two major concerns when dealing with triangulation: efficiency and minimality. By efficiency we mean how fast can we obtain a legal triangulation, i.e., one that partitions the given region into

*Current address: Department of Mechanical Engineering, Sophia University, Chiyoda-ku, Tokyo, 102 Japan.

+ On leave from Osaka Electra-Communication University, Hatsu-cho, Neyagawa, Osaka, 512 Japan.

221

Ol%-6774/86 $3.00 Copyright 0 1986 by Academic Press, Inc.

All right.9 of rcpduction in any form resaved.

(3)

222 ÂSANO, ÂSANO, ÂNP ^PINTER

triangles alone, regardless of how many such triangles will be produced.

Minimality is the problem of finding the absolute minimum number of triangles required for the partitioning; in this, one must take advantage of collinearities between edges and vertices to capture the fine details of the geometry. In this paper we shed some light on these aspects of the triangulation problem and on the relationship between them.

Garey, Johnson, Preparata, and Tarjan [2] resolved the efficiency problem by divising an 0( n log n) algorithm for partitioning a simple polygon into (exactly) n - 2 triangles. Their algorithm can be extended to deal with polygonal regions with holes within the same time complexity. Our first result shows that their time bound is optimal for polygons with holes in the sense that an Q(n log n) lower bound exists for any triangulation algorithm.

The lower bound problem for the hole-free case remains open.

As for minimality, not much research has been reported. Most authors define a triangulation to be a maximal subset of chords no two of which intersect inside the polygon. In some applications, the upper bound on the number of triangles guaranteed that way, namely n - 2 for a hole-free polygon, seems to suffice. However, if minimality is our objective, factors of 2 can be easily gained in extreme cases by omitting unnecessary splits of triangles whose sides are unions of collinear chords or edges of the original polygon (see Fig. 1). Even more dramatic savings are observed when holes are allowed (and the guaranteed bound goes up to n - 2 + 2k for n vertices and k holes), justifying some effort in this direction. The second contribution of our paper is an algorithm for the minimum-number-partitioning of a polygonal region with holes that runs in time polynomial in the number of vertices for a fixed number of holes.

In addition, we introduce the distinction between chordal triangulations, in which only lines that connect two vertices of the original polygon are allowed, as opposed to arbitrary triangulations, where intermediate vertices (“Steiner points”) can be used within the body of the polygon or along its

edges to support lines of the partitioning. Here the interplay between

--- --- --- --- _---- v

FIG. 1. This 12-vertex polygon can be partitioned into 6 rather than 10 triangles; in general, we can achieve n/2 instead of n - 2.

(4)

efficiency and minimality is even more dramatic, since the search space becomes much larger.

2. A LOWER BOUND FOR THE TRIANGULATION PROBLEM In this section we show that Q(n log n) operations are necessary to triangulate a polygonal region which may have holes. It is shown below that the sorting problem on n positive integers can be transformed in linear time into the problem of triangulating a polygonal region with 3n + 3 vertices and n holes. It is well known that the lower bound for the sorting problem is a(n log n).

Consider the set of n (n 2 3) positive, distinct integers X = { Xl, x 2,“‘, x, }. Let m be the smallest and M be the largest among them.

We construct a polygonal region P(X) as follows. The external boundary of P(X) is a triangle specified by three vertices u0 = (0, 0), u1 = (4M - 2m - 1,2M - l), and u2 = (4M - 2m - 1, -2M + 1). P(X) contains n trian- gular holes, each consisting of three vertices uJi = (2xi + LO), uji+i = (2x;, xi), and u3i+2 = (2xi, -xi), 1 I i I n. An example of such a polygonal region is illustrated in Fig. 2. We can triangulate this polygonal region P(X) in several ways. Assume that we had a triangulation of P(X) in the

Y m I

---cj)(

IM-2m-1

FIG. 2. A polygonal region P(X) with 3n + 3 vertices and n holes.

(5)

224 ÂSANO, ÂSANO, ÂND ^PINTER

form of a set C of chords and each chord was given by a couple of labels attached to the two endpoints of the chord (that is, the chord (i, j) is the line segment between two vertices u, and uj). For each chord (i, j), x( ui) <

x( uj) is assumed, where x(u) is the x coordinate of the vertex of u.

Using the set C of chords, we can sort the given numbers xi, x2,. . . , x, in the following way. First, we prepare an array r such that r(3i) = r(3i + 1) = r(3i + 2) = i for each i, 0 I i I n, that is, r(j) = k means that the vertex u, corresponds to the kth datum xk and r(j) = 0 means that uj is on the external boundary. Next, for each chord (i, j) in C such that i mod 3 = 0 and i > 0, we set NEXT(r(i)) = r(j). Here note that the vertex ui such that i mod 3 = 0 and i > 0 must be a middle vertex of some hole, and there are only two vertices visible from it, as shown in Fig. 3.

Since the interior angle at any middle vertex exceeds 180 degree, there must be at least one chord incident upon every such vertex. It is easily seen in Fig. 3 that if uj is visible from a middle vertex ui and r(j) > 0, that is, uj is a hole’s vertex, then the next largest datum of xrcij is x,(~), which is established by the substitution NEXT(r(i)) = r(j). Thus, by tracing the array NEXT, we can sort the data xi, x2,. . . , x, in the increasing order, which takes only O(n) time.

Here it should be noted that in the above proof we allow O(n) holes for the polygonal region. The lower bound for the problem of triangulating a polygonal region which contains a fixed number of holes (including 0) has not been settled.

FIG. 3. There are two visible vertices from each middle vertex of a hole

(6)

3. MINIMUM NUMBER TRIANGULATION OF POLYGONAL REGIONS The problem of partitioning a polygonal region which may contain holes into a minimum number of triangles is known to be NP-complete [4].

However, for a polygonal region with a fixed number of holes, we can construct a polynomial time exact algorithm using a dynamic programming approach. Fortunately, we can modify the method developed in [l, pp.

314-3211 for minimum edge-length triangulation by changing the cost function and allowing triangles with zero area.

First, we present an O(n3) time algorithm for hole-free polygons (simple polygonal regions with no holes), where n is the number of vertices. Next, we show that there exists an O(n3+2h ) time exact algorithm for polygonal regions with h holes and n vertices.

Consider a polygon P with n vertices u,,, ui, . . . , un-i, in clockwise order.

Let Pi, t denote a subpolygon of P which is formed by P’s edges C”j? uj+l)~(“i+l~ uj+2)Y’*‘P (ui+,-2, Ui+t-1) and the segment (vi, Ui+t-I), where we take all subscripts to be computed modulo n. A subpolygon Pi, I is called a valid subpolygon when the segment ( ui, ui+,- i) is an edge or chord of P, where a chord is defined to be a segment between two vertices of P which lies entirely within P. Notice that a chord may lie on the boundary of P. By ri, , we denote the size of the minimum number triangulation of Ti, ! if Pi, I is a valid subpolygon. Otherwise, ri, f is defined to be positive infimte.

The problem here is to compute rO, n. In the algorithm we shall describe below we compute all ri, I. Before calculating each ri, ,, we check the validity of the subpolygon Pi, ,. Note that Pi,, is valid if and only if the line segment (ui, u,+,-~) intersects no edge of the polygon P and one internal point on the line ( ui, u;+~-& lies inside P. Thus, it requires only O(n) time to check whether Pi, t is valid or not. If Pi, f is not valid then we set ri, f = 00.

Otherwise, that is, if Pi,, is valid, we compute ri,r by a dynamic programming approach based on the fact that in any triangulation of Pi,, there exists a triangle that contains the side ( ui, ui+,-i). Here we allow a dummy triangle the area of which is zero. For example, in the polygon P,,s shown in Fig. 4, the triangle ( uO, u2, uq) is a dummy triangle.

Now, let Pi, I be valid. We have only to consider decompositions of Pi,, by (u;, uk) and (uk, ui++i) which may be edges or chords of Pi,,, where i+Ilk<i+t-2. When k=i+l or k=i+t-2,Pi,, is decomposed into two parts, that is, in the former case into a triangle

C”i* “i+lY ~;+~-i) and a subpolygon Pi+l,r-l, and in the latter case into a

subpolygon Pi,t-l and a triangle (ui, u~+,-~, u,+~-~). When i + 2 I k 5 i + t - 3, Pi,, is decomposed into three parts Pi,k-i+l, Pk,t-k+i, and a triangle (ui, uk, u~+,-~), as shown in Fig. 5. In particular, if a triangle

C”i9 ui+17 ~;+~-i) is a dummy triangle, then we have

ri,t = Ti+l,t-l*

(7)

“1

-;:)i ________--- - --- --

"0 “4 “2

“3

FIG. 4. A polygon I’,,, s with a dummy triangle ( u, , u2, q).

For the same reason, if a triangle (ui, u~+~-~, ui++t) is a dummy triangle, we have

‘i,t = ri r-l.

Furthermore, a triangle ( ui, uk, u+-~), i + 2 S k I i + t - 3, may happen to be a dummy triangle. Therefore, we introduce another symbol di, j, k defined by

di,j,k=O if(ui,uj,uk)isadummytriam$k

= 1 otherwise.

Here it should be noted that if ( ui, uk) ((u,, u~+~-~), respectively) is not an edge nor chord of I’,,,, then the subpolygon ^{Pi, k-i+l} (Pk,l-k+i, respectively) is not valid and ri, k-i+l = cc (rk,l-k+i = cc, respectively). Thus, we

P k,t-k+i

FIG. 5. Decomposition of a subpolygon P,, , into three parts: two subpolygons, Pi. k _, + 1 and Ph.,-h+,, and a triangle (u,, ukr u,+,-1).

(8)

FIG. 6. A polygon to illustrate the algorithm of Section 3.

can compute ri, f by the following formula:

ri I = min[7i+1.t-1 + di,i+l,i+l-l, 5, r-l + di,i+r-2,i+t-l,

An efficient way to solve the triangulation problem follows from the above discussion. We make a table giving T~,~, the size of the minimum number triangulation of

Pi t

for all i and t, 0 I i I n - 1 and 3 < t I n.

Since the solution to any given problem depends only on the solution to problems of smaller size, we can fill in the table in ascending order of t, that is, t = 3,4,. . . , n. In order to find a set of chords to triangulate

P

optimally,

FIG. 7. Table of q, ,‘s.

(9)

228 ASANO, ASANO, AND PINTER

(b)

7

(cl (d

(e)

FIG. 8. Illustrative example: (a) original polygon; (b) decomposition of PO 9 into PL.s and Tri(0, 1,8); (c) decomposition of P,,, into P2,, and Tri(l,2,8); (d) decomposiiion of Pz,, into P2.6 and a dummy triangle (2,7,8); (e) decomposition of P2.6 into P,,, and Tri(2,3,7); and (f) decomposition of P3. 5 into P3. 3, P,,, , and a dummy triangle (3,5,7).

we have only to store an optimal chord to achieve the minimum number decomposition of each subpolygon Pi, f. Each TV, I can be computed in O(n) time and the table size is O(n*). Thus, the complexity of the above described algorithm based on dynamic programming is O(n3).

Consider the example shown in Fig. 6 to demonstrate the algorithm.

Figure 7 shows the costs T~,~‘s. Thus, we find that the polygon is decomposed into five triangles. Such a decomposition is derived as shown in Fig. 8.

Next, we propose an O(n3+2h ) time algorithm for partitioning a polygonal region with h holes into a minimum number of triangles. We already presented such an algorithm for the case of h = 0. We assume that there exists an O(n3+2h’ ) time exact algorithm for polygonal regions with h’ holes

(10)

FIG. 9. Resultant polygonal region P’ after adding a chord to a polygonal region P.

where h’ -C h. Now, consider a polygonal region P with h holes. Our algorithm is based on the fact that in any triangulation there exists at least one triangle ( ui, uj, uk) such that ( ui, uj) is an edge of a specified hole of P and uk is not any vertex of the hole. When we decompose P by such a triangle we obtain a polygonal region P’ with at most h - 1 holes. If the new P’ has coincident vertices, then P’ may be considered to be the polygonal region, as shown in Fig. 9. It is easily verified that the existence of coincident vertices is compatible with the dynamic programming approach.

By the hypothesis we can find the minimum number triangulation of P’ in O(n 3+ ‘ch- ‘)) time. The number of such triangles is less than n* even in the worst case, and we can obtain the representation of P’ in O(n) time. We can enumerate such triangles in O(n3) time as follows: For each edge ( ui, uj) of the specified hole of P, find a set of vertices which are not on the hole and visible from both ui and uj. Then, if uk is such a vertex, ( ui, uj, uk) is a triangle required if both of ( ui, uk) and ( uj, uk) are chords.

Thus, we can find a minimum number triangulation of P by performing the process in ^O(n3) time and then solving at most n* subproblems each in O(n 3+2(h-1)) time. This leads to the algorithm required.

4. ARBITRARY TRIANGULATIONS

In this section we raise the following question: What happens when lines other than chords (or diagonals) are allowed to participate in the partitioning? Then we are free to generate internal vertices (so called “Steiner points”) in order to take into account effects as shown in Fig. 10. The question is how deep one has to go in looking for such points? Figure 11 shows that it is not enough to look at extensions of edges and their intersections-we must also look at “second-order” diagonals that connect such new vertices.

(11)

FIG. 10. Collinearities between extensions of edges can be exploited to reduce the number of triangles from 6 to 4.

It still remains open how many times should one iterate such a step, i.e., how long do we have to keep drawing higher order diagonals between previous intersections in order to reveal further collinearities. We conjecture, that the examples of Figs. 10 and 11 can be extended to show that for any given integer k, there exists a (hole-free) polygon for which this process must be repeated k times if a true minimum is to be found. We suspect, though, that the number of vertices will grow (at least) quadratically with k, giving rise to yet another conjecture, namely that it is enough to repeat the process only O(6) times for a polygon with n vertices. This could serve as the basis for a dynamic programming algorithm for the problem, in which all the new diagonals will be considered, similarly to the treatment of

“original” diagonals in the chordal case. Although the running time of such an algorithm could grow exponentially with the size of the polygon, proving the conjecture would establish the nature of a well-defined search space for the arbitrary triangulation problem.

FIG. 11. The only way to achieve 14 triangles for this 24 vertex polygon is by connecting the intersections of the edge extensions.

(12)

5. CONCLUSIONS AND RELATED PROBLEMS

We can summarize the result of our paper as follows: no triangulation can be achieved faster than sorting, so the algorithm from [2] should be used if all we need is a chordal triangulation. If, however, one wants to find the smallest number of triangles into which a figure can be partitioned, full advantage must be taken of collinearities at a potential penalty in running time.

Finally, we would like to draw the reader’s attention to a related family of problems, namely: minimum edge-length triangulations of polygons. Here we want to obtain a triangulation as before, but the optimality criterion is different: the total length of the lines drawn to describe the partitioning must be minimized. Klincsek [3], and later Aho, Hopcroft, and Ulhnan [l], presented chordal solutions based on dynamic programming, whose running time was O( n3). Lingas [4] showed that the problem in general is NP-complete if holes are allowed, and the related minimum weight triangulation problem of a point set is still open. Here we pose the problem of how hard is it to find a minimum edge-length arbitrary triangulation of a simple, hole-free polygon.

ACKNOWLEDGMENTS

The third author would like to thank Andrzej Lingas and Paris Kanellakis for helpful discussions.

REFERENCES

1. A. V. AHO, J. E. HOPCROFT, AND J. D. ULLMAN, “Data Structures and Algorithms,”

Addison-Wesley, Reading, Mass., 1983.

2. M. R. GAREY, D. S. JOHNSON, F. P. PREPARATA, AND R. E. TARJAN, Triangulating a simple polygon, Inform. Process. ht. 7, No. 4 (1978), 175-179.

3. G. T. KLINCSEK, Minimal triangulations of polygonal domains, Ann. Discrete Math. Vol. 9, pp. 121-123, North-Holland, Amsterdam/New York, 1980.

4. A. LINGAS, Advances in minimum weight triangulation, in “Linkoping Studies in Science and Technology No. 97, 1983,” Bergholm, Sweden.