Pseudotriangle

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. Thus, it is a shape bounded by three inward-curved sides, formed by the boundaries of these three convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation 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, the terms as used here were introduced in 1993 by Michel Pocchiola and Gert Vegter in connection with the computation of visibility relations and bitangents among convex obstacles in the plane. Pointed pseudotriangulations were first considered by Ileana 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 and for dynamic graph drawing and shape morphing.…

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. Thus, it is a shape bounded by three inward-curved sides, formed by the boundaries of these three convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation 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, the terms as used here were introduced in 1993 by Michel Pocchiola and Gert Vegter in connection with the computation of visibility relations and bitangents among convex obstacles in the plane. Pointed pseudotriangulations were first considered by Ileana 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 and for dynamic graph drawing and shape morphing. Pointed pseudotriangulations arise in rigidity theory as examples of minimally rigid planar graphs, and in methods for placing guards in connection with the art gallery theorem. The shelling antimatroid of a planar point set gives rise to pointed pseudotriangulations, although not all pointed pseudotriangulations can arise in this way. For a detailed survey of much of the material discussed here, see Rote, Santos, and Streinu (2008). A pointed pseudotriangulation with v vertices must have exactly 2v − 3 edges. This follows by a simple double counting argument involving the Euler 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 2e angles, of which all but v are convex. Thus, 3f − 3 = 2e − v. Combining this with the Euler equation f − e + v = 2 and solving the resulting simultaneous linear equations gives e = 2v − 3. The same argument also shows that f = v − 1 (including the convex hull as one of the faces), so the pseudotriangulation must have exactly v − 2 pseudotriangles. 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 2k − 3 edges. Thus, pointed pseudotriangulations satisfy the conditions defining Laman graphs: they have exactly 2v − 3 edges, and their k-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. 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. 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 ith 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.

See also

Deltoid curve Circular triangle . Preliminary version in Ninth ACM Symp. Computational Geometry (1993) 328–337. . . . . . . . . .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1359429197 under CC BY-SA 4.0; modifications have been made.