Maximum weight triangulation of a special convex polygon

Maximum Weight Triangulation of A Sp eial Convex Polygon 1 Jianb o Qian 2 and Cao An Wang 3 . Abstrat In this pap er, we investigate the maximum weight triangulation of a sp eial onvex p olygon, alled `semi-irled onvex p olygon'. We prove that the maximum weight triangulation of suh a p olygon an b e found in O ( n 2 ) time. 1 Intro dution Triangulation of a set of p oints is a fundamental struture in omputational geometry. Among dierent triangulations, the minimum weight triangulation ( M W T for short) of a set of p oints in the plane attrats sp eial attention [1,2,3℄. The onstrution of the M W T of a p oint set is still an outstanding op en problem. When the given p oint set is the set of verties of a onvex p olygon (so-alled onvex point set ), then the orresp onding M W T an b e found in O ( n 3 ) time by dynami programming [1,2℄. On the ontrast, there is not muh researh done on maximum weight triangulation ( M AT for short). From the theoretial viewp oint, the maximum weight triangulation problem and the minimum weight triangulation problem attrats equally interest, and one seems not to b e easier than the other. The study of maximum weight triangulation will help us to understand the nature of optimal triangulations. The rst work in the M AT [4℄ showed that if an n -sided p olygon P insrib ed on a irle, then M AT ( P ) an b e found in O ( n 2 ) time. In this pap er, we study the M AT of the following sp eial onvex p olygon: let P b e a onvex n  sided p olygon suh that the entire p olygon P is ontained inside the irle with an edge of P as diameter. We all suh a p olygon as semi-irled . We prop ose an O ( n 2 ) algorithm for omputing the M AT ( P ) of a semi-irled onvex p olygon P . Reall that a straightforward dynami programming metho d will take O ( n 3 ) to nd M AT ( P ). 1 This work is supp orted by NSERC grant OPG0041629 and the National Natural Siene Foundation of China under Grant No. 70221001. 2 Institute of Applied Mathematis, Chinese Aademy of Siene, Beijing, China. (email: jb qianmail.amss.a.n) 3 Department of Computer Siene, Memorial University of Newfoundland, St. John's, Newfoundland, Canada A1B 3X5 (email: wanggareld.s.mun.a) 1 2 Preliminaries Let S b e a set of p oints in the plane. A tr iang ul ation of S , denoted by T ( S ), is a maximal set of non-rossing line segments with their endp oints in S . It follows that the interior of the onvex hull of S is partitioned into non-overlapping triangles. The weight of a triangulation T ( S ) is given by ! ( T ( S )) = X s i s j T ( S ) ! ( i; j ) ; where ! ( i; j ) is the Eulidean length of line segment s i s j . A maximum weight triangulation of S ( M AT ( S )) is dened as for all p ossible T ( S ), ! ( M AT ( S )) = max f ! ( T ( S )) g . p1pn pk pi Figure 1: An illustration of semi-irled onvex p olygon. Let P b e a onvex p olygon (whose verties form a onvex point set ) and T ( P ) b e its triangulation. A semi-irled onvex polygon P is a sp eial onvex p olygon suh that its longest edge is the diameter and all the edges of P lie inside the semi-irle with this longest edge as diameter. (Refer to Figure 1). The following two prop erties are easy to verify for a semi-irled onvex p olygon P = ( p 1 ; p 2 ; :::; p k ; :::; p n  1 ; p n ). Prop erty 1: Let p i p k for 1  i<k  n b e an edge in P . Then the area b ounded by p i p k and hain ( p i ; :::; p k ) is a semi-irled onvex p olygon. Prop erty 2: In P , edge p i p j for 1  i<j <n or 1 < i < j  n is shorter than p 1 p n . 3 Finding an MAT of a semi-irled onvex p olygon Lemma 1 Let P = ( p 1 ; p 2 ; :::; p k ; :::; p n  1 ; p n ) be a semi-irled onvex polygon. Then, one of the edges: p 1 p n  1 and p n p 2 must belong to its maximum weight triangulation M AT ( P ) . pro of: Supp ose for ontradition that none of the two extreme edges: p 1 p n  1 and p n p 2 b elongs to M AT ( P ). Then, there must exist a vertex p k for 2 < k < n  1 suh that b oth p 1 p k and p n p k b elong to M AT ( P ). Without loss of generality, let p k lie on one side 2 p1 p1 pk pn−1 p2 pn pk pn−1 p2 pn LR C (a) (b) R Figure 2: For the pro of of Lemma 1. of the p erp endiular bisetor of edge p 1 p n , say the lefthand side (if p k is on the bisetor, the following argument is still appliable), The two edges p 1 p k and p n p k partition P into three areas, denoted by R; L; and C . Both L and R are semi-irled onvex p olygons by Prop erty 1. (Refer to part (a) of Figure 2.) Let the edges of M AT ( P ) lying inside area L b e ( e 1 ; e 2 ; :::; e k  3 ) and let E L = ( e 1 ; e 2 ; :::; e k  3 ; p 1 p k ). Let E  L denote the edges: ( p n p 2 ; p n p 3 ; :::; p n p k  1 ). Then, there is a p erfet mathing b etween E L and E  L . This is b eause E L and E  L resp etively triangulate the same area L [ C , hene the numb er of internal edges of the two triangulations must b e equal. Let us onsider a pair in the mathing ( e i ; p n p j ) for 1 < i; j < k . It is not hard to see that ! ( e i ) < ! ( n; j ) b eause any edge in E L is shorter than p 1 p k by Prop erty 2, any edge in E  L is longer than p n p k , and p n p k is longer than p 1 p k (due to p k lying on the lefthand side of the p erp endiular bisetor of p 1 p n ). Therefore, ! ( E L ) is less than ! ( E  L ). Now, we shall onstrut a new triangulation, say T ( P ), whih onsists of all the edges in M AT ( P ) exept replaing the edges of E L by E  L . We have that ! ( T ( P )) > ! ( M AT ( P )), whih ontradits the M AT ( P ) assumption. Then, suh a p k annot exist and one of p 1 p n  1 and p n p 2 must b elong to M AT ( P ). 2 By Lemma 1 and by Prop erty 1, we have a reurene for the weight of a M AT ( P ). Let ! ( i; j ) denote the weight of the M AT ( P i;j ) of a semi-irled onvex p olygon P i;j = ( p i ; p i +1 ; :::; p j ). Let ! ( i; j ) denote the length of edge p i p j . ! ( i; j ) = 8 < : ! ( i; i + 1) j = ( i + 1) max f ! ( i; j  1) + ! ( j  1 ; j ) ; ! ( i + 1 ; j ) + ! ( i; i + 1) g + ! ( i; j ) otherwise It is a straight-forward matter to design a dynami programming algorithm for nding the M AT ( P ). ALGORITHM M AT  F I N D ( P ) Input: a semiirled onvex n  sided p olygon: ( p 1 ; :::; p n ). Output: M AT ( P ). Metho d: 1. for i = 1 to n  1 do ! ( i; i + 1) = ! ( i; i + 1) 3 2. for l = 2 to n  1 do 3. for i = 1 to n  l do ! ( i; i + l ) = max f ! ( i; i + l  1) + ! ( i + l  1 ; i + l ) ; ! ( i + 1 ; i + l ) + ! ( i; i + 1) g + ! ( i; i + l ) 4. Identify the edges of M AT ( P ) by heking the ! 's. 5. end. Sine the lo op indies i and l range roughly from 1 to n and eah evaluation of ! ( i; j ) takes onstant time, all ! ( i; j ) for 1  i; j  n an b e evaluated in O ( n 2 ) time. If we reord these ! 's, we an nd the edges in M AT ( P ) by an extra O ( n ) time to examine the reord. Therefore, we have the following theorem. Theorem 1 The maximum weight triangulation of a semi-irled onvex n  gon P , M AT ( P ) , an be found in O ( n 2 ) time. Pro of: The orretness is due to Prop erty 1. It is lear that the numb er of exeutions of Step 3 dominates the time omplexity. The numb er of exeutions is ( n  3) + ( n  4) + ::: +2+1) O ( n 2 ). 2 4 Conlusion In this pap er, we prop osed an O ( n 2 ) dynami programming algorithm for onstruting the M AT ( P ) of a semi-irled onvex n  sided p olygon. It is still an op en problem whether one an design an o ( n 3 ) algorithm for nding the M AT ( P ) for a general onvex n  sided p olygon P . Referenes [1℄ Gilb ert P., New results on planar triangulations, Teh. Rep. ACT-15 (1979), Co ord. Si. Lab., University of Illinois at Urbana. [2℄ Klinsek G., Minimal triangulations of p olygonal domains, Annual Disrete Mathematis 9 (1980) pp. 121-123. [3℄ Preparata F. and Shamos M., Computational Geometry (1985), Springer-Verlag. [4℄ Wang C., Chin F., and Yang B., Maximum Weight triangulation and graph drawing, The Information Proessing Letters , 70(1999) pp. 17-22. 4