On the number of pseudo-triangulations of certain point sets

On the Number of Pseudo-Triangulations of Certain Point Sets 1 Oswin Aichholzer a,2, David Orden ∗,b,3, Francisco Santos c,3and Bettina Speckmann d aInstitute for Software Technology, Graz University of Technology, Austria. bMathematics Department, University of Alcal´a, Spain. cDepartment of Mathematics, Statistics and Computer Science, University of Cantabria, Spain dDepartment of Mathematics and Computer Science, Eindhoven University of Technology Abstract We compute the exact number of pseudo-triangulations for two prominent point sets, namely the so-called double circle and the double chain. We also derive a new asymptotic lower bound for the maximal number of pseudotriangulations which lies significantly above the related bound for triangulations. Key words: Counting, Pseudo-triangulations, Triangulations, Double circle, Double chain. 1. Introduction Pseudo-triangulations, a.k.a. geodesic triangulations, generalize triangulations and have found multiple applications in Computational Geometry in the last years. They were originally studied in the context of visibility [10,11] and ray shooting [5,6], but have been used in kinetic collision detection [1,8], rigidity [16], and guarding [15]. Apseudo-triangle is a polygon with exactly three vertices, called corners, with internal angles less than π. A pseudo-triangulation of a set Sof points in the plane is a partition of the convex hull of S into pseudo-triangles whose vertex set is exactly S. A vertex is called pointed if it has an adjacent angle greater than π.Pointed pseudo-triangulations, are the ones with all vertices pointed. The set of all pseudo-triangulations of a point set has somewhat nicer properties than that of all tri- ∗Corresponding author Email addresses: [email protected] (Oswin Aichholzer), [email protected] (David Orden), [email protected] (Francisco Santos), [email protected] (Bettina Speckmann). 1Parts of this work were done while the authors visited the Departament de Matem`atica Aplicada II, Universitat Polit`ecnica de Catalunya. 2Research partially supported by Acciones Integradas 2003-2 004, Proj.Nr.1/2003 3Research partially supported by Acci´on Integrada Espa˜na-Austria HU2002-0010 and grant BFM2001-1123 of Spanish Direcci´on General de Investigaci´on Cient´ıfica angulations. For example, pseudo-triangulations of a point set with nelements form the vertex set of a certain polyhedron of dimension 3n−3 [9]. The diameter of the graph of pseudo-triangulations is O(nlog n) [3] versus the Θ(n2) diameter of the graph of triangulations of certain point sets. For standard triangulations it is not know which sets of points have the fewest or the most triangulations, but it was shown in [2] that sets of points in convex position minimize the number of pointed pseudo-triangulations. Let Abe a point set and let AIbe its subset of interior points. The pseudo-triangulations of Acan naturally be stratified into 2AIsets. More precisely, for each subset W⊆AIwe denote by PTW(A) the set of pseudo-triangulations of Ain which the points of Ware pointed and those of AI\Ware non-pointed. For example, PT∅(A) is the set of triangulations of Aand PT AI(A) is the set of pointed pseudo-triangulations of A. The following conjecture is implicit in previous work: Conjecture 1 For every point set Ain general position in the plane, the cardinalities of PTW(A) are monotone with respect to W. That is to say, for any W⊆AIand for every v∈W, one has |PTW(A)| ≥ |PTW\{v}(A)|. Note that [12] proves the following inequality in the other direction: 3|PTW\{v}(A)| ≥ |PTW(A)|. 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry In this paper we compute the number of pseudotriangulations, and so check Conjecture 1, for two prominent point sets, namely those with the asymptotically maximal and minimal number of triangulations known so far: 1.1. Points in almost convex position. For any given pair of numbers (v, i), 3 ≤i≤v, a point set in almost convex position with parameters (v, i) consists of the vvertices of a convex vgon and a set of iinterior points, placed sufficiently close to idifferent edges of the v-gon. This is a special case of the “almost-convex polygons” studied in [7]. There it is shown that the number of triangulations of such a point set does not depend on the choice of the iedges of the vgon. Indeed, if we call this number n(v, i) one has n(v, i) = n(v+ 1, i −1) −n(v, i −1) and from this n(v, i) can be computed recursively, starting with n(v, 0) = Cv−2(the Catalan number). The array obtained by this recursion (difference array of Catalan numbers) appears in Sloane’s Online Encyclopedia of Integer Sequences [14] with ID number A059346 (note that there n(v, i) appears for every i≥0 and v≥2, although only the cases v≥max{i, 3}have an interpretation as counting triangulations). Asymptotically, n(v, i) equals 4v3i, modulo a polynomial factor. The extremal case with v=i=n/2 (referred to as double circle), has asymptotically Θ(√12nn−3/2) triangulations. It is conjectured in [4] that this is the smallest number of triangulations that a point set with npoints can have. 1.2. Double chain. For any two numbers l, m ≥0, a double chain is a convex 4-gon with land mpoints, respectively, placed forming concave chains next to opposite edges of the 4-gon in a way that the they do not cross the two diagonals of the convex 4-gon (see Fig. 1). The double chain decomposes into a convex l+2-gon, a convex m+2-gon, and a non-convex l+m+4-gon, which have Cl,Cm, and l+m+2 l+1 triangulations respectively. Hence, the double chain has ClCml+m+ 2 l+ 1  triangulations. In the extremal case l=m= (n− 4)/2 this gives Θ(8nn−7/2). This is (asymptotically) the point set with the largest number of triangulations known so far. Fig. 1. A double chain: l= 5 and m= 4. 2. The double circle and its relatives Fix two integers i, v, 3 ≤i≤v, and let Abe a point set in almost convex position with parameters (v, i). Let pbe a specific interior point of A and let qr be the convex hull edge which has pnext to it. Let Band Cbe the point sets obtained respectively by deleting pfrom Aand by moving p to convex position across the convex hull edge qr: p r q A r q B p r q C Fig. 2. The point sets A,Band C. Here v= 9 and i= 4. Lemma 2 Let Wbe a set of interior points of A not containing p(so that Wis also a set of interior points of Band C). Then: (i) |PTW(A)|=|PTW(C)|−|PTW(B)|. (ii) |PTW∪{p}(A)|= 2 |PTW(C)|−|PTW(B)|. Corollary 3 (i) Asatisfies Conjecture 1. (ii) The numbers |PTW(A)|depend only on v,i and k:= |W|. We omit the proofs of these and other results due to the limited space available for this abstract. Let n(v, i, k) denote the numbers referred to in part 2 of the corollary. Since n(v, i, 0) = 4v3i(modulo a polynomial factor) and since n(v, i, k) = 2(v+ 1, i −1, k −1) −n(v, i −1, k −1), we conclude that n(v, i, k)∼4v3i−k7k,modulo a polynomial factor. Adding the numbers over all the possible subsets of interior points gives i X k=0 i k4v3i−k7k= 4v10i. Hence, a double circle (the case i=v=n/2) has √28npointed pseudo-triangulations and √40n pseudo-triangulations in total, modulo a polynomial factor. March 25-26, 2004 Seville (Spain) 3. The single chain As a step towards the study of the double chain, let us start with a single chain. By this we mean a point set Awith three extremal vertices and a concave chain of lpoints next to an edge. Equivalently, a convex l+ 2-gon together with a point in its exterior and which sees all but one of its edges. We call this special point the top point and denote it by p. Let p0,...,pl+1 be the rest of the points, numbered from left to right, so that the interior points are p1,...,pl. We define AI={p1,...,pl}. We are particularly interested in the pointed pseudo-triangulations of the single chain. We classify them according to which interior points are joined to the top. For any subset W⊂AIwe denote by PPTW(A) the set of pointed pseudotriangulations of Ain which pis joined to piif and only if pi∈W. Clearly, PPT ∅(A) is in bijection to the set of triangulations of the convex l+ 2-gon, hence its cardinality is the Catalan number Cl. Lemma 4 For every W: |PTW(A)|=X W′⊂W|PPTW′(A)|. Hence, Conjecture 1 holds for A. As a special case of this lemma, |PT∅(A)|= |PPT∅(A)|. That is to say, triangulations of Aare in bijection to triangulations of the convex l+ 2gon. Curiously enough, PPTAI(A) (that is, the pointed pseudo-triangulations in which the top point pis joined to everything), have the cardinality of the next Catalan number Cl+1, and flips between them form the graph of the corresponding associahedron (see [13], Section 5.3 and the remark and picture on pp. 728–729). The following is a 1-dimensional analog of Conjecture 1. Conjecture 5 For every W⊂AIand p∈AI\W, |PPTW∪{v}(A)| ≥ |PPT W(A)|. Unfortunately, we do not know how to compute the numbers PPTW(A), or even recursive formulae for them. But we can compute the sum of all the PPTW(A)’s for each cardinality of W. Theorem 6 Let a(l, i) := P|W|=i|PPTW(A)|. (i) a(l, 0) = Cl, and a(l, 1) = (l+ 1)Cl. (ii) For every i≥2, a(l, i) = l+ 1 iCl−a(l−1, i −2). Part 2 of Theorem 6 allows to compute all the values of a(l, i) recursively, starting from those stated in part 1. The following table shows the first few values: l\i0 1 2 3 4 5 Pl i=0 a(l, i) 0 1 1 1 1 2 3 2 2 6 5 13 3 5 20 28 14 67 4 14 70 135 120 42 381 5 42 252 616 770 495 132 2307 The recursion also tells us that the array a(l, i) coincides with the sequence with ID A062991 in [14]. There, we learn that the row sums, that is, the numbers |PTAI(A)|of pointed pseudotriangulations of these point sets, form the sequence A062992 and satisfy: |PTAI(A)|= 2 l X j=0 (−1)l−jCj2j−(−1)l. Corollary 7 The following inequalities hold for the number of pointed pseudo-triangulations of a single chain of linterior points, l≥2: 2lCl<2l+1Cl−2lCl−1<|PTAI(A)|<2l+1Cl. In particular, the number is in Θ(8ll−3/2). 4. The double chain Let Abe a double chain with land minterior points in the two chains, resp. (so Ahas l+m+ 4 points in total). We call the l+ 2 and m+ 2 vertices in the two chains the “top” and “bottom” parts. We show how to count the number of pointed pseudo-triangulations of A. Let us call Band Csingle chains with land m interior points each. Bcan be considered the subset of Aconsisting of the top part plus a bottom vertex, and analogously for C. Every pseudo-triangulation TAof Ainduces pseudo-triangulations TBand TC of Band Cas follows: consider on the one hand all the pseudo-triangles of TAthat use at most one vertex of the bottom, and contract these vertices to a single one. Do the same for pseudo-triangles with at most one vertex in the top (see Fig. 3). Conversely, given a pair of pseudo-triangulations of Band C, if i(resp. j) denotes the number of interior edges incident to the bottom (resp. top) point, there are exactly i+j+2 i+1 ways to recover a pseudo-triangulation of Afrom that data, by shuf- 20th European Workshop on Computational Geometry Fig. 3. Decomposing double chain pseudo-triangulations. fling the i+ 1 pseudo-triangles of TBincident to the bottom and the j+1 of TCincident to the top. Theorem 8 Let Vand Wbe subsets of the top and bottom interior points. For each V′⊂Vand W′⊂ Wlet tV,W V′,W ′=l−|V\V′|+m−|W\W′|+2 l−|V\V′|+1 . Then: |PTV∪W(A)|=X V′⊂V W′⊂W tV,W V′,W ′|PPTV′(B)||PPT W′(C)|. Corollary 9 If Conjecture 5 holds, then the double chain satisfies Conjecture 1. For pointed pseudo-triangulations of the double chain, Theorem 8 says that: |PTAI(A)|= l X i=0 m X j=0 i+j+ 2 i+ 1 a(l, i)a(m, j), where a(·,·) is as in the previous section. The sequence for l=mis 2,38,1476,81310,5495276,424398044,... In order to analyze the asymptotics of this sequence we need the following lemma on the numbers a(l, i): Lemma 10 1−i(i−1) (4l−2)(l−i+ 2) ≤a(l, i) l+1 iCl≤1 Corollary 11 Let Abe a double chain with n points and with equal numbers on both sides (that is to say, l=m= (n−4)/2). Then: Ω(12nn−9/2)≤ |PTAI(A)| ≤ O(12nn−3/2). References [1] P. K. Agarwal, J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang. Deformable free space tilings for kinetic collision detection. In Proc. 5th Workshop Algorithmic Found. Robotics (A. K. Peters, 2001) 83–96. [2] O. Aichholzer, F. Aurenhammer, H. Krasser, and B. Speckmann. Convexity Minimizes PseudoTriangulations. In Proc. 14th Canad. Conf. Comp. Geom. (2002) 158–161. [3] O. Aichholzer, F. Aurenhammer, and H. Krasser. Adapting (pseudo)-triangulations with a near-linear number of edge flips. In Lecture Notes in Computer Science 2748, Proc. 8th International Workshop on Algorithms and Data Structures (WADS), volume 2748 (2003) 12–24. [4] O. Aichholzer, H. Krasser. The point-set order-type database: A collection of applications and results. In Proc. 13th Canad. Conf. Comp. Geom. (2001) 17–20. [5] B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica 12 (1994) 54–68. [6] M. Goodrich and R. Tamassia. Dynamic ray shooting and shortest paths in planar subdivision via balanced geodesic triangulations. J. of Algorithms 23 (1997) 51–73. [7] F. Hurtado andM. Noy. Counting triangulations of almost-convex polygons. Ars Combinatoria 45 (1997) 169–179. [8] D. Kirkpatrick, J. Snoeyink, and B. Speckmann. Kinetic collision detection for simple polygons. Intern. Journal Comp. Geom. Appl. 12 (2002) 3–27. [9] D. Orden and F. Santos. The polytope of noncrossing graphs on a planar point set. Preprint 2003, http://arxiv.org/abs/math.CO/0302126, accepted in Discrete Comput.Geom. [10] M. Pocchiola and G. Vegter. Minimal tangent visibility graphs. Comput. Geom. Theory Appl. 6(1996) 303– 314. [11] M. Pocchiola and G. Vegter. Topologically sweeping visibility complexes via pseudo-triangulations. Discrete Comp. Geom. 16 (1996) 419–453. [12] D. Randall, G. Rote, F. Santos and J. Snoeyink. Counting triangulations and pseudo-triangulations of wheels. In Proc. 13th Canad. Conf. Comput. Geom. (2001) 149–152. [13] G. Rote, F. Santos, and I. Streinu. Expansive motions and the polytope of pointed pseudotriangulations. Discrete and Computational Geometry – The Goodman-Pollack Festschrift, (B. Aronov, S. Basu, J. Pach, M. Sharir, eds), Algorithms and Combinatorics, Springer Verlag, Berlin, 699–736, 2003. [14] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. Copyright 2003 AT&T, http://www.research.att.com/˜njas/sequences [15] B. Speckmann and C. D. T´oth. Allocating vertex πguards in simple polygons via pseudo-triangulations. In Proc. 14th Symp. Disc. Alg. (2003) 109–118. [16] I. Streinu. A combinatorial approach to planar noncolliding robot arm motion planning. In Proc. 41st FOCS (2000) 443–453.