Jump to content

Pseudotriangle

From Wikipedia, the free encyclopedia
The pseudotriangle between three smooth convex sets (left), and a polygonal pseudotriangle (right).

InEuclidean plane geometry,apseudotriangle(pseudo-triangle) is thesimply connectedsubset of theplanethat lies between any three mutually tangentconvex sets.Apseudotriangulation(pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and apointed pseudotriangulationis a pseudotriangulation in which at each vertex the incident edges span anangleof less than π.

Although the words "pseudotriangle" and "pseudotriangulation" have been used with various meanings in mathematics for much longer,[1]the terms as used here were introduced in 1993 by Michel Pocchiola and Gert Vegter in connection with the computation of visibility relations andbitangentsamong convex obstacles in the plane. Pointed pseudotriangulations were first considered byIleana Streinu(2000, 2005) as part of her solution to thecarpenter's ruler problem,a proof that anysimple polygonal pathin the plane can be straightened out by a sequence of continuous motions. Pseudotriangulations have also been used for collision detection among moving objects[2]and for dynamic graph drawing and shape morphing.[3]Pointed pseudotriangulations arise inrigidity theoryas examples of minimally rigidplanar graphs,[4]and in methods for placing guards in connection with theart gallery theorem.[5]Theshelling antimatroidof a planar point set gives rise to pointed pseudotriangulations,[6]although not all pointed pseudotriangulations can arise in this way.

For a detailed survey of much of the material discussed here, see Rote,Santos,andStreinu(2008).

Pseudotriangles

[edit]

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 topolygonsas 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 isconvexif it spans an interior angle of less than π, andconcaveotherwise (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, anytriangle,and any nonconvexquadrilateral,is a pseudotriangle.

Theconvex hullof any pseudotriangle is a triangle. The curves along the pseudotriangle boundary between each pair of convex vertices either lie within the triangle or coincide with one of its edges.

Pseudotriangulations

[edit]

Apseudotriangulationis a partition of a region of the plane into pseudotriangles. Anytriangulationof 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 ann-vertex polygonal pseudotriangle, then a pseudotriangulation of it may have as few as one pseudotriangle andnedges, or as many asn− 2 pseudotriangles and 2n− 3 edges.

Aminimal pseudotriangulationis a pseudotriangulationTsuch that no subgraph ofTis a pseudotriangulation covering the same convex region of the plane. A minimal pseudotriangulation withnvertices must have at least 2n− 3 edges; if it has exactly 2n− 3 edges, it must be a pointed pseudotriangulation, but there exist minimal pseudotriangulations with 3n− O(1) edges.[7]

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

[edit]
A shelling sequence of a planar point set and the pointed pseudotriangulation derived from this sequence.

Apointed pseudotriangulationcan 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 abitangentline segment could be added between two vertices of the face.

A pointed pseudotriangulation withvvertices must have exactly 2v− 3 edges.[8]This follows by a simpledouble countingargument involving theEuler characteristic:as each face but the outer one is a pseudotriangle, with three convex angles, the pseudotriangulation must have 3f− 3 convex angles between adjacent edges. Each edge is the clockwise edge for two angles, so there are a total of 2eangles, of which all butvare convex. Thus, 3f− 3 = 2e−v.Combining this with the Euler equationf−e+v= 2 and solving the resultingsimultaneous linear equationsgivese= 2v− 3. The same argument also shows thatf=v− 1 (including the convex hull as one of the faces), so the pseudotriangulation must have exactlyv− 2 pseudotriangles.

Similarly, since anyk-vertex subgraph of a pointed pseudotriangulation can be completed to form a pointed pseudotriangulation of its vertices, the subgraph must have at most 2k− 3 edges. Thus, pointed pseudotriangulations satisfy the conditions definingLaman graphs:they have exactly 2v− 3 edges, and theirk-vertex subgraphs have at most 2k− 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.[9]

Another way of finding a pointed pseudotriangulation is toshella 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 theshelling antimatroidof 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.[6]However, not all pointed pseudotriangulations can be formed in this way.

Aichholzer et al. (2004) show that a set ofnpoints,hof which belong to theconvex hullof the set, must have at leastCh−2×3n−hdifferent pointed pseudotriangulations, whereCidenotes theithCatalan 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.[10]

See also

[edit]

Notes

[edit]
  1. ^For "pseudo-triangle" see, e.g., Whitehead, J. H. C.(1961), "Manifolds with transverse fields in Euclidean space",Annals of Mathematics,73(1): 154–212,doi:10.2307/1970286,JSTOR1970286,MR0124917. On page 196 this paper refers to a "pseudo-triangle condition" in functional approximation. For "pseudo-triangulation" see, e.g.,Belaga, È. G. (1976), "[Heawood vectors of pseudotriangulations]",Doklady Akademii Nauk SSSR(in Russian),231(1): 14–17,MR0447029.
  2. ^Agarwal et al. (2002).
  3. ^Streinu (2006).
  4. ^Haas et al. (2005)
  5. ^Speckmann and Tóth (2005).
  6. ^abHar-Peled (2002).
  7. ^Rote, Wang, Wang, and Xu (2003), Theorem 4 and Figure 4.
  8. ^First shown by Streinu (2000), but the argument we give here is from Haas et al. (2005), Lemma 5.
  9. ^Haas et al. (2005).
  10. ^Bereg (2005); Brönnimann et al. (2006).

References

[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Pseudotriangle&oldid=1117724851"