A Linear-Time Near-Optimum-Length Triangulation Algorithm for Convex Polygons

of 10

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
10 pages
0 downs
A Linear-Time Near-Optimum-Length Triangulation Algorithm for Convex Polygons
  See discussions, stats, and author profiles for this publication at:https://www.researchgate.net/publication/220573255 A Linear-Time Near-Optimum-LengthTriangulation Algorithm forConvex Polygons.  Article   in  Journal of Computer and System Sciences · October 1994 DOI: 10.1016/S0022-0000(05)80052-2 · Source: DBLP CITATION 1 READS 7 1 author: Vitit KantabutraIdaho State University 6   PUBLICATIONS   35   CITATIONS   SEE PROFILE All content following this page was uploaded by Vitit Kantabutra on 30 June 2015. The user has requested enhancement of the downloaded file.  JOURNAL OF COMPUTER AND SYSTEM SCIENCES 49, 325--333 (1994) A Linear-Time Near-Optimum-Length Triangulation Algorithm for Convex Polygons VITIT KANTABUTRA Department of Computer Science, State University of New York, Brockport, New York 14420 Received July 20, 1990; revised August 17, 1993 This paper shows how to compute a short triangulation for a convex polygon in O(n) time, where n is the number of sides of the input polygon. The resulting triangulation is guaranteed to be of a total length that is only a constant factor of the shortest possible. © 1994 Academic Press, Inc, 1. INTRODUCTION In this paper we show how to compute a short triangulation for a convex polygon in O(n) computational steps, where n is the number of sides of the input polygon. The resulting triangulation is guaranteed to be of a total length that is only a constant factor of the shortest possible. According to Aho, Hopcroft, and Ullman [1], such short triangulations have applications in the area of shading. It is well known [1] that by using dynamic programming we can compute a triangulation of minimum length in O(n 3) steps. 2. A SPECIAL CASE To understand the algorithm for triangulating general convex polygons, it is helpful to begin by considering a special case of an (n + 1)-sided polygon, in which there is a very long side s and in which the two sides adjacent to s make angles that are less than some e, where ~ is less than 90°; see Fig. 1. Call the polygon sides other than s by the names of s 1, s2 ..... sn from left to right, as shown in Fig. 1. Let the length of the projections of si onto s be pi. We will consider the problem of triangulating the polygon so that the sum of the lengths of all the projections of the triangulation edges onto s is at most a constant factor fi of the minimum possible. It is easy to show that the length of such a triangulation T' can only be a constant factor of the length of any minimum-length triangulation T. (Let I T'I be the sum of the edge lengths of the triangulation T'. We assumed that the length of the projection of [T'] ~<fl× length of projection of ]To[, where To is the triangulation 325 0022-0000/94 $6.00 Copyright © 1994 by Academic Press, Inc. All rights of reproduction in any form reserved.  326 VITIT KANTABUTRA v S V si V i i I FIG. 1. A special case. with minimum projection. Thus IT'[ cos c~<fl ITo]; that is, IT'[ ~<fl ITol/cos ~. But since To is the minimum-projection triangulation, we have I Tol cos c~ ~< I TI Com- bining the last two relations yields [T'I ~< fl [Tl/cos 2 ~, which proves the desired statement.) In order to construct T', we will identify the triangulations with the extended binary trees (binary trees in which no node has exactly one child) with n leaves, as follows: the polygon sides sl .... , s, are identified with the leaves in left-to-right order. And if vivj, vjvk, vivk (i<j<k) are triangulation edges (which means that some of these could also be polygon sides), then the nodes identified with the first two edges are respectively made the left and the right children of a new node, which is the node identified with the third edge vivk. Suppose we let the tree's leaf weights be equal to the lengths of the projections of the corresponding polygon sides (the pi's). Then the projected length of the triangulation plus the projected polygon side lengths is equal to the tree weight. In linear time we can obtain a suboptimum (up to within a constant factor of the optimum) binary tree I-2]. Thus this is what we will do. 3. THE GENERAL CASE Let a convex polygon P be input. In order to find a near-optimum triangulation, we will first draw a frame (some line segments joining some polygon vertices) and then we find a triangulation T that includes this frame (a triangulation includes the frame if all the frame's line segment are triangulation edges) and is no longer than some constant times the shortest triangulation that includes the frame. Both the frame and T will each be computed in O(n) time. The length of T will be within a constant factor of the length of the optimum triangulation. To prove this assertion, we will show the following: If there is any triangulation T' of the input polygon P, then we can find a triangulation T of P such that T includes the frame and the length of T is only a constant times the length of T'. It follows that the shortest triangulation of P that includes the frame is of length at most a constant times the shortest triangulation of P. And thus T, whose length is within a constant factor of the length of the shortest triangulation that includes  ALGORITHM FOR CONVEX POLYGONS 327 the frame, must also be of length within some constant factor of the shortest triangulation of P. 3.1. Constructing the Frame The frame can be constructed in a number of steps that is linear in the number of sides of the input polygon P according to the following steps: 1. Find the longest diagonal D (ties broken arbitrarily) of P. Assume without loss of generality that D is horizontal and that there is some polygon vertex below D. The diagonal D will not be a part of the frame and may not even be a part of the triangulation, but will be used as a convenient reference. 2. Let v be the leftmost polygon vertex below D. If possible, draw a line from v up, making a 60 ° angle with the horizontal, until another vertex, v', of P is hit. If this is not possible, then draw two lines up from v to two other vertices of P so that these lines make angles with the horizontal as close to 60 ° as possible; one just less than 60 ° and the other just greater than 60 °. Let v' be the vertex pertaining to the angle less than 60 ° 3. If v' is not the right end vertex of D, then draw a line or two down from v' to another vertex of P, like in Step 2 above, except that the angle that these lines make with the horizontal is now approximately -60 ° instead of + 60 °. 4. Repeat the zigzag pattern as many times as possible; see Fig. 2. The work we have done so far has divided P into several regions. Some regions (like (3) and (5)) may be triangles, in which case there is no further subdivision to be done. The other regions may have to be subdivided further, even in the stage of making the frame. There are two end regions, which are regions (1) and (9) in Fig. 2. For each non-triangle, non-end region, do the following: (a) Add the line segment s (which will now be called the base that joins the two extreme vertices B and C of the chain of P's vertices in the region, as shown in Fig. 3. (For illustration purposes, assume that the sides of P in this region are on the bottom, below the base of the region. Also assume that s is horizontal.) FXG. 2. The frame.  328 VITIT KANTABUTRA A C / e z -~ 90 ° O~ _< 90 ° FIG. 3. A non-triangle, non-end region. (b) Let 01 and 0 2 be the angles that s makes with the sides of P adjacent to S, as shown in Fig. 3. These two angles must be less than 90 °. If both these angles are at most 45 °, then stop. Otherwise, go to step 5. 5. Assume, without loss of generality, that 01 is greater than 45 ° (02 may also be greater than 45°). Let Sl be the side of P adjacent to B, as shown in Fig. 4. Try to draw a line from B to a vertex v' of P, so that this line makes an angle of 45 ° magnitude with s. If this is impossible, then draw two lines from B down to two vertices of P, so that these lines make angles as close as possible to 45 ° to s; one line makes an angle just less than 45 °, while the other makes an angle just greater than 45 ° degrees; see Fig. 4. Suppose that the former line ends at vertex v and that the latter line ends at vertex v'. (These vertices have nothing to do with the vertices of the same names used in the explanation of an earlier part of the paper.) Then from v' draw a line (or two), again making an angle of approximately 45 ° with the side of P that is incident to v' and points to the left (Fig. 4). Repeat this process as long as we stay within the region bounded by BC. Obviously this process can be repeated no more than three times due to the amount of turning involved each time. In fact, in the fourth repetition only one (and never two) line can be drawn if that repetition even exists at all. We can see that this step divides that region into no more than eight parts. Some parts are triangles and do not have to be subdivided any further. c B V FI~. 4. Dividing the subregion under the base.
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks