Pseudotriangle

In Euclidean plane geometry, a pseudotriangle is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation of a convex polygon in which at each vertex the incident edges span an angle of less than π.

Although the words "pseudotriangle" and "pseudotriangulation" have been used with various meanings in mathematics for much longer, [For "pseudo-triangle" see, e.g., cite journal
author = Whitehead, J. H. C.
title = Manifolds with transverse fields in Euclidean space
journal = Annals of Mathematics
volume = 73
issue = 1
year = 1961
pages = 154–212
id = MathSciNet | id = 0124917
doi = 10.2307/1970286On page 196 this paper refers to a "pseudo-triangle condition" in functional approximation. For "pseudo-triangulation" see, e.g., cite journal
author = Belaga, È. G.
title = Heawood vectors of pseudotriangulations
journal = Dokl. Akad. Nauk SSSR
volume = 231
year = 1976
issue = 1
pages = 14–17
id = MathSciNet | id = 0447029] the terms as used here were introduced in 1993 by Pocchiola and Vegter in connection with the computation of visibility relations and bitangents among convex obstacles in the plane. Pointed pseudotriangulations were first considered by Streinu (2000, 2005) as part of her solution to the carpenter's ruler problem, a proof that any simple polygonal path in the plane can be straightened out by a sequence of continuous motions. Pseudotriangulations have also been used for collision detection among moving objects [Agarwal et al. (2002).] and for dynamic graph drawing and shape morphing. [Streinu (2006).] Pointed pseudotriangulations arise in rigidity theory as examples of minimally rigid planar graphs, [Haas et al. (2005)] and in methods for placing guards in connection with the art gallery theorem. [Speckmann and Tóth (2005).] The shelling antimatroid of a planar point set gives rise to pointed pseudotriangulations, [Har-Peled (2002).] although not all pointed pseudotriangulations can arise in this way.

For a detailed survey of much of the material discussed here, see Rote et al (2006).

Pseudotriangles

Pocchiola and Vegter (1996a,b,c) originally defined a pseudotriangle to be a simply-connected region of the plane bounded by three smooth convex curves that are tangent at their endpoints. However, subsequent work has settled on a broader definition that applies more generally to polygons as well as to regions bounded by smooth curves, and that allows nonzero angles at the three vertices. In this broader definition, a pseudotriangle is a simply-connected region of the plane, having three convex vertices. The three boundary curves connecting these three vertices must be convex, in the sense that any line segment connecting two points on the same boundary curve must lie entirely outside or on the boundary of the pseudotriangle. Thus, the pseudotriangle is the region between the convex hulls of these three curves, and more generally any three mutually tangent convex sets form a pseudotriangle that lies between them.

For algorithmic applications it is of particular interest to characterize pseudotriangles that are polygons. In a polygon, a vertex is "convex" if it spans an interior angle of less than π, and "concave" otherwise (in particular, we consider an angle of exactly π to be concave). Any polygon must have at least three convex angles, because the total exterior angle of a polygon is 2π, the convex angles contribute less than π each to this total, and the concave angles contribute zero or negative amounts. A polygonal pseudotriangle is a polygon that has exactly three convex vertices. In particular, any triangle, and any nonconvex quadrilateral, is a pseudotriangle.

The convex hull of any pseudotriangle is a triangle. Each of the three convex vertices is connected by a boundary curve that either lies within the triangle or coincides with one of its edges.

Pseudotriangulations

A pseudotriangulation is a partition of a region of the plane into pseudotriangles. Any triangulation of a region of the plane is a pseudotriangulation. While any two triangulations of the same region must have the same numbers of edges and triangles, the same is not true of pseudotriangulations; for instance, if the region is itself an "n"-vertex polygonal pseudotriangle, then a pseudotriangulation of it may have as few as one pseudotriangle and "n" edges, or as many as "n" − 2 pseudotriangles and 2"n" − 3 edges.

A "minimal pseudotriangulation" is a pseudotriangulation "T" such that no subgraph of "T" is a pseudotriangulation covering the same convex region of the plane. A minimal pseudotriangulation with "n" vertices must have at least 2"n" − 3 edges; if it has exactly 2"n" − 3 edges, it must be a pointed pseudotriangulation, but there exist minimal pseudotriangulations with 3"n" − O(1) edges. [Rote, Wang, Wang, and Xu (2003), Theorem 4 and Figure 4.]

Agarwal et al. (2002) describe data structures for maintaining pseudotriangulations of moving points or moving polygons. They show that using pseudotriangulations in place of triangulations allows their algorithms to maintain these structures with relatively few combinatorial changes as the inputs move, and they use these dynamic pseudotriangulations to perform collision detection among the moving objects.

Gudmundsson et al. (2004) consider the problem of finding a pseudotriangulation of a point set or polygon with minimum total edge length, and provide approximation algorithms for this problem.

Pointed pseudotriangulations

A pointed pseudotriangulation can be defined as a finite non-crossing collection of line segments, such that at each vertex the incident line segments span an angle of at most π, and such that no line segments can be added between any two existing vertices while preserving this property. It is not hard to see that a pointed pseudotriangulation is a pseudotriangulation of its convex hull: all convex hull edges may be added while preserving the angle-spanning property, and all interior faces must be pseudotriangles else a bitangent line segment could be added between two vertices of the face.

A pointed pseudotriangulation with "v" vertices must have exactly 2"v" − 3 edges. [First shown by Streinu (2000), but the argument we give here is from Haas et al. (2005), Lemma 5.] This follows by a simple argument involving the Euler characteristic: as each face but the outer one is a pseudotriangle, with three convex angles, the pseudotriangulation must have 3"f" − 3 convex angles between adjacent edges. Each edge is the clockwise edge for two angles, so there are a total of 2"e" angles, of which all but "v" are convex. Thus, 3"f" − 3 = 2"e" − "v". Combining this with the Euler equation "f" − "e" + "v" = 2 and solving the resulting simultaneous linear equations gives "e" = 2"v" − 3.

Similarly, since any "k"-vertex subgraph of a pointed pseudotriangulation can be completed to form a pointed pseudotriangulation of its vertices, the subgraph must have at most 2"k" − 3 edges. Thus, pointed pseudotriangulations satisfy the conditions defining Laman graphs: they have exactly 2"v" − 3 edges, and their "k"-vertex subgraphs have at most 2"k" − 3 edges. Laman graphs, and therefore also pointed pseudotriangulations, are minimally rigid graphs in two dimensions. Every planar Laman graph can be drawn as a pointed pseudotriangulation, although not every planar drawing of a planar Laman graph is a pseudotriangulation. [Haas et al. (2005).]

Another way of finding a pointed pseudotriangulation is to "shell" a point set; that is, to remove convex hull vertices one by one until all points have been removed. The family of sequences of removals that can be formed in this way is the shelling antimatroid of the point set, and the set of edges of convex hulls of the sequence of point sets formed by this removal process forms a pseudotriangulation. [Har-Peled (2002).] However, not all pointed pseudotriangulations can be formed in this way.

Aichholzer et al. (2004) show that a set of "n" points, "h" of which belong to the convex hull of the set, must have at least "C"_"h"−2×3^"n"−"h" different pointed pseudotriangulations, where "C_i" denotes the "i"th Catalan number. As a consequence, they show that the point sets with the fewest pointed pseudotriangulations are the vertex sets of convex polygons. Aichholzer et al. (2006) investigate point sets with large numbers of pointed pseudotriangulations. Computational geometry researchers have also provided algorithms for listing all pointed pseudotriangulations of a point set in a small amount of time per pseudotriangulation. [Bereg (2005); Brönnimann et al. (2006).]

Notes

References

*cite journal
author = Agarwal, Pankaj K.; Basch, Julien; Guibas, Leonidas J.; Hershberger, John; Zhang, Li
year = 2002
title = Deformable free-space tilings for kinetic collision detection
journal = International Journal of Robotics Research
volume = 21
issue = 3
pages = 179–197
doi = 10.1177/027836402320556395

*cite journal
author = Aichholzer, Oswin; Aurenhammer, Franz; Krasser, Hannes; Speckmann, Bettina
title = Convexity minimizes pseudo-triangulations
journal = Computational Geometry Theory and Applications
volume = 28
issue = 1
year = 2004
pages = 3–10
doi = 10.1016/j.comgeo.2004.01.002
id = MathSciNet | id = 2070708. [http://www.cccg.ca/proceedings/2002/03.ps Preliminary version in Canad. Conf. Comput. Geom., 2003]

*cite journal
author = Aichholzer, Oswin; Orden, David; Santos, Francisco; Speckmann, Bettina
title = On the number of pseudo-triangulations of certain point sets
year = 2006
id = arxiv|math.CO|0601747

*cite journal
author = Bereg, Sergey
title = Enumerating pseudo-triangulations in the plane
journal = Computational Geometry Theory and Applications
volume = 30
issue = 3
pages = 207–222
year = 2005
doi = 10.1016/j.comgeo.2004.09.002
id = MathSciNet | id = 2123970

*cite journal
author = Brönnimann, Hervé; Kettner, Lutz; Pocchiola, Michel; Snoeyink, Jack
title = Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm
journal = SIAM J. Comput.
volume = 36
year = 2006
issue = 3
pages = 721–739
doi = 10.1137/050631008
id = MathSciNet | id = 2263009

*cite conference
author = Gudmundsson, Joachim; Levcopoulos, Christos; Kamal, Lodaya; Meena, Mahajan
title = Minimum weight pseudo-triangulations
booktitle = FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
publisher = Springer-Verlag, Lecture Notes in Computer Science 3328
date = 2004
pages = 299–310
doi = 10.1007/b104325
url = http://www.win.tue.nl/~hgudmund/HP_links/PAPERS/FSTTCS04.pdf

*cite journal
author = Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter
title = Planar minimally rigid graphs and pseudo-triangulations
journal = Computational Geometry Theory and Applications
volume = 31
issue = 1–2
pages = 31–61
year = 2005
doi = 10.1016/j.comgeo.2004.07.003
id = MathSciNet | id = 2131802
*cite journal
author = Har-Peled, Sariel
title = A comment on pseudo-triangulation in three dimensions
year = 2002
url = http://valis.cs.uiuc.edu/~sariel/papers/02/ptriang/

*cite journal
author = Pocchiola, Michel; Vegter, Gert
title = The visibility complex
journal = International Journal of Computational Geometry and Applications
volume = 6
issue = 3
year = 1996a
pages = 297–308
doi = 10.1142/S0218195996000204
id = Preliminary version in [http://portal.acm.org/citation.cfm?id=160985.161159 Ninth ACM Symp. Computational Geometry (1993) 328–337] .
url = http://www.di.ens.fr/~pocchiol/postscript/pv-vc-93.ps

*cite journal
author = Pocchiola, Michel; Vegter, Gert
year = 1996b
title = Topologically sweeping visibility complexes via pseudotriangulations
journal = Discrete and Computational Geometry
volume = 16
pages = 419–453
id = MathSciNet | id = 1414964

*cite conference
author = Pocchiola, Michel; Vegter, Gert
date = 1996c
title = Pseudo-triangulations: theory and applications
booktitle = Proceedings of the 12th Annual ACM Symposium on Computational Geometry
pages = 291–300
doi = 10.1145/237218.237398
url = http://www.cs.rug.nl/~gert/research/postscript/pv-ptta-96.ps.gz

*cite conference
author = Rote, Günter; Santos, Francisco; Streinu, Ileana
title = Expansive motions and the polytope of pointed pseudo-triangulations
booktitle = Dicrete and Computational Geometry — The Goodman–Pollack Festschrift
publisher = Springer-Verlag
date = 2003
pages = 699–736
id = arxiv|math.CO|0206027

*cite journal
author = Rote, Günter; Santos, Francisco; Streinu, Ileana
title = Pseudo-triangulations — a survey
year = 2006
id = arxiv|math.CO|0612672

*cite conference
author = Rote, Günter; Wang, Cao An; Wang, Lusheng; Xu, Yinfeng
title = On constrained minimum pseudotriangulations
booktitle = Computing and Combinatorics
date = 2003
publisher = Springer-Verlag, Lecture Notes in Computer Science 2697
pages = 445–454
url = http://www.inf.fu-berlin.de/inst/ag-ti/uploads/tx_tipublications/On_constrained_minimum_pseudotriangulations.pdf
*cite journal
author = Speckmann, Bettina; Tóth, Csaba D.
title = Allocating vertex π-Guards in simple polygons via pseudo-triangulations
year = 2005
journal = Discrete and Computational Geometry
volume = 33
issue = 2
pages = 345–364
doi = 10.1007/s00454-004-1091-9
id = MathSciNet | id = 2121300

*cite conference
author = Streinu, Ileana
title = A combinatorial approach to planar non-colliding robot arm motion planning
booktitle = Proceedings of the 41st Annual Symposium on Foundations of Computer Science
publisher = IEEE Computer Society
date = 2000
pages = 443–453
doi = 10.1109/SFCS.2000.892132
url = http://cs.smith.edu/~streinu/Papers/motion.ps

*cite journal
author = Streinu, Ileana
title = Pseudo-triangulations, rigidity and motion planning
journal = Discrete and Computational Geometry
volume = 34
year = 2005
issue = 4
pages = 587–635
doi = 10.1007/s00454-005-1184-0
id = MathSciNet | id = 2173930

*cite conference
author = Streinu, Ileana
title = Parallel-redrawing mechanisms, pseudo-triangulations and kinetic planar graphs
booktitle = Proc. Int. Symp. Graph Drawing (GD 2005)
pages = 421–433
publisher = Springer-Verlag, Lecture Notes in Computer Science 3843
year = 2006