3D realization of two triangulations of a onvex polygon

3D realization of two triangulations of a onvex p olygon. Sergey Bereg a , a Department of Computer Siene, University of Texas at Dal las, Box 830688, Rihardson, TX 75083, USA. Abstrat We study the problem of onstrution of a onvex 3-p olytop e whose (i) shadow b oundary has n verties and (ii) two hulls, upp er and lower, are isomorphi to two given triangulation s of a onvex n -gon. Barnette [1℄ proved the existene of a onvex 3-p olytop e in general ase. We show that, in our ase, a p olytop e an b e onstruted using an op eration of edge reation. Key words: triangulation, onvex p olytop e, Steinitz theorem 1. Intro dution Let P b e a onvex p olygon in the xy -plane with n verties. Two triangulations of P are alled distint if the only edges they share are the edges of P . Let T 1 and T 2 b e two distint triangulations of P . At the First Canadian Conferene on Computational Geometry Leo Guibas onjetured that it is always p ossible to p erturb the verties of P vertially out (i.e., by displaements parallel to the z -axis) so that the p olygon P b eomes a spatial p olygon P 0 suh that the onvex hull of P 0 is a onvex p olyhedron onsisting ot two triangulated ups glued along P 0 , and the triangulation of the upp er up (i.e., those faes oriented toward + z ) is that sp eied as T 1 , and the triangulation of the lower up is that sp eied as T 2 [4℄. Boris Bekster [2℄ disproved Guibas' onjeture by showing a ounterexample, a onvex hexagon with two triangulations. Marlin and Toussaint [3℄ onsidered the omputational problem of deiding whether a triple ( P ; T 1 ; T 2 ) admits a realization in R 3 . They redued the problem to a linear programming problem with O ( n 2 ) inequality onstraints and n variables. The variables are z -o ordinates of lifted verties of P and the onstraints orrep ond to vertex-fae relations: the verties must b e b elow/ab ove the planes passing through faes of the Email address: besputdallas.edu (Sergey Bereg). URL: http://utdallas.edu/~sxb027100 (Sergey Bereg). upp er/lower up of P 0 . The numb er of onstraints an b e dropp ed to 2 n  6 = j T 1 j + j T 2 j by onsidering dihedral angles orresp onding to diagonals of the triangulations [7℄. Guibas onjeture is related to Steinitz's theorem [5℄. Steinitz's Theorem: A graph G is isomorphi to the edge graph of a onvex 3-polytope if and only if G is 3-onneted and planar. By Steinitz's theorem the graph ( P ; T 1 [ T 2 ) is the edge graph of a onvex 3-p olytop e [3℄. Aording to Barnette's theorem [1℄, every 3-p olytop e with a Hamiltonian iruit has realization suh that the Hamiltonian iruit is a shadow b oundary. This implies that Guibas' onjeture is true up to a ombinatorial deformation [2℄. Formally this an b e stated as follows. Theorem 1 For any two distint triangulations T 1 and T 2 of a onvex polygon P 2 in R 2 with n verties, there is a onvex polytope P 3 in R 3 with n verties suh that (i) the xy -shadow S of P 3 ontains al l its verties, and (ii) there is a isomorphism  : P 2 ! S that maps the edges of T 1 (resp. T 2 ) to the edges of the upper hul l of P 3 (resp. the lower hul l). Barnette's pro of deals with general faes (not just triangles) due to its generality. In this pap er we give a dierent pro of of Theorem 1 that uses only triangular faes of p olytop es whih an b e turned into a more robust algorithm for nding a ombinatorial realization of ( P ; T 1 ; T 3 ) in R 3 . Realization questions have b een studied in om- 20th EWCG Seville, Spain (2004) 20th Europ ean Workshop on Computational Geometry puter graphis and sene analysis as well. Sugihara [6℄ established neessary and suÆient onditions whether a line drawing in the plane an b e realized in R 3 by lifting. We all a triple ( P ; T 1 ; T 2 ) a onguration . We all a map  satisfying the onditions of Theorem 1 a realization . 2. Edge ontration (a) (b) p1 p2 p3 p1 p2 p3 Fig. 1. (a) Edge ontration of a triangulation. (b) Edge ontration of two triangulations. The diagonals of one triangulation are solid and the diagonals of the other triangulation are dashed. As in Barnette's pro of we use the op eration of edge removal. The dierene is that we will not apply it for diagonals of P . This prevents the app earene of faes with more than three verties. The edge ontration in a onguration is dened by idetifying the edge enp oints. If applied to one triangulation of P , it pro dues a triangulation, see Fig. 1 (a) for example where the edge p 1 p 2 is ontrated. When applied for two triangulations, we want the redued triangulations to b e distint. An edge e of a onguration ( P ; T 1 ; T 2 ) is ontratible if the new triangulations T 0 1 and T 00 2 are distint. In general, not all edges are ontratible. For example, the edge p 1 p 2 in the Fig. 2 (a) is not ontratible sine two edges p 1 p 6 and p 2 p 6 from dierent triangulations oinide after the ontration of p 1 p 2 . p1 p2 p3 p4 p5 p6 p7 p1 p2 p3 p4 p1=p4 p2 p3 (a) (b) Fig. 2. (a) The edge ( p 1 ; p 2 ) is not ontratible. (b) The edge ontration for n = 4. Lemma 2 Let C be a onguration with n  4 verties. There is a ontratible edge of C among the edges of the onvex polygon. PROOF. If n = 4 then every edge of the onvex p olygon is ontratible, see Fig. 2 (b). We prove the lemma for n  5. Supp ose to the ontrary that there is a onguration ( P ; T 1 ; T 2 ) suh that all edges of P are not ontratible. Let p 1 ;:::;p n b e Marh 25-26, 2004 Seville (Spain) the verties of P in lo kwise order. The edge p 1 p 2 is not ontratible. Then there is a vertex p k ; 4  k  n  1 suh that p 1 p k is an edge of one triangulation, say T 1 , and p 2 p k is an edge of T 2 , see Fig. 3 (a). Consider an edge p i p i +1 ; 2  i  k  1. Sine p i p i +1 is not ontratible, there is a vertex p  ( i ) suh that p i p  ( i ) is a diagonal of T j ; j = 1 ; 2 and p i +1 p  ( i ) is a diagonal of T 3  j , see Fig. 3 (a). We all p  ( i ) a witness sine it indiates that p i p i +1 is not ontratible. At least one vertex of f p i ; p i +1 g , say p l , is dierent from p 2 and p k . Then the edge p l p  ( i ) do es not ross one of the edges p 1 p k or p 2 p k . Therefore  ( i ) is an index in the range 1 ;:::;k . p1 p2 pk P pi pi+1 pc(i) pi pi+1 pi+2 pc(i+1) pc(i) p1pk (a) (b) e1 e2 Fig. 3. Lemma 2. We all p  ( i ) a left witness if  ( i ) < i . We all p  ( i ) a right witness if  ( i ) > i + 1. Eah witness is either left or right sine  ( i ) 6 = i; i + 1. Note that p  (2) is a right witness and p  ( k  1) is a left witness. Thus there is an index i; 2  i  k  2 suh that p  ( i ) is the right index and p  ( i +1) is the left index, see Fig. 3 (b). Then p i p  ( i ) , a diagonal of a triangulation T j , intersets b oth diagonals e 1 = ( p i +1 ; p  ( i +1) ) and e 2 = ( p i +2 ; p  ( i +1) ). Either e 1 or e 2 is a diagonal of T j . Contradition. 3. Edge reation We dene an op eration of edge reation as the reverse op eration of the edge ontration. The following lemma hraterizes the hange of the on- guration when an edge is reated. We denote the sequene of indies from i to j in lo kwise order by f i; i + 1 ;:::;j g . Lemma 3 (Edge reation) Let C = ( P ; T 1 ; T 2 ) be a onguration with n  3 verties where P = f p 1 ;:::;p n g . Suppose that an edge e = ( q 1 ; q 2 ) is reated in plae of a vertex p i 2 P . Let C 0 = ( P 0 ; T 0 1 ; T 0 2 ) be the onguration obtained by repla- ing a vertex p i by an edge e = ( q 1 ; q 2 ) in lokwise order. Then there are two edges ( p i ; p j ) 2 T 1 and ( p i ; p k ) 2 T 2 suh that { an edge ( p l ; p i ) 2 T 1 ; l 2 f i + 1 ; i + 2 ;:::;j g is replaed by the edge ( p l ; q 1 ) 2 T 0 1 , and { an edge ( p l ; p i ) 2 T 1 ; l 2 f j; j + 1 ;:::;i  1 g is replaed by the edge ( p l ; q 2 ) 2 T 0 1 , and { an edge ( p l ; p i ) 2 T 2 ; l 2 f i + 1 ; i + 2 ;:::;p k g is replaed by the edge ( p l ; q 1 ) 2 T 0 2 , and { an edge ( p l ; p i ) 2 T 2 ; l 2 f k ; k + 1 ;:::;i  1 g is replaed by the edge ( p l ; q 2 ) 2 T 0 2 . We show that an edge an b e always reated. Theorem 4 Let C = ( P ; T 1 ; T 2 ) be a onguration with n  3 verties and let  : P ! R 3 be its realization in R 3 . Let C 0 = ( P 0 ; T 0 1 ; T 0 2 ) be the on- guration obtained by an edge reation. There is a realization of C 0 if there is a realization of C . Theorem 1 follows from Theorem 4. Referenes [1℄ D. W. Barnette. Pro jetions of 3-p olytop es. Israel J. Math. , 8:304{308, 1970. [2℄ B. V. Dekster. Convex hulls of spatial p olygons with a xed onvex pro jetion. Beitrage zur Algebra und Geometrie/Contributions to Algebra and Geometry , 36:123{124, 1995. [3℄ B. Marlin and G. Toussaint. Construting onvex 3- p olytop es from two triangulations of a p olygon. In Pro. 20th Europ ean Workshop on Computational Geometry pi−1 pi pi+1 pjpk pi−1 q1 pi+1 pjpk q2e Fig. 4. Edge reation. 14th Canad. Conf. Comput. Geom. , pp. 36{39, 2002, http://www.g.a/proeedings/2002/28.ps . [4℄ W. J. Moser. Problems, problems, problems. Disrete Applied Mathematis , 31:201{225, 1991. [5℄ E. Steinitz and H. Rademaher. Vorlesungen uber die Theorie der Polyeder . Julius Springer, Berlin, Germany, 1934. [6℄ K. Sugihara. A neessary and suÆient ondition for a piture to represent a p olyhedral sene. IEEE Trans. on Pattern Analysis and Mah. Intel ligene , 6(5):578{ 586, 1984. [7℄ G. Toussaint. Personal ommuniation.