Pseudotriangle
Encyclopedia
Euclidean geometry
Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...
, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
s. A pseudotriangulation (pseudo-triangulations) 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, the terms as used here were introduced in 1993 by Pocchiola and Vegter in connection with the computation of visibility relations and bitangent
Bitangent
In mathematics, a bitangent to a curve C is a line L that touches C in two distinct points P and Q and that has the same direction to C at these points...
s 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
Carpenter's ruler problem
The carpenter's rule problem is a discrete geometry problem, which can be stated in the following manner: Can a simple planar polygon be moved continuously to a position where all its vertices are in convex position, so that the edge lengths and simplicity are preserved along the way? A closely...
, 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
Antimatroid
In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included...
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 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 polygonPolygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
s 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
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
, and any nonconvex quadrilateral
Quadrilateral
In Euclidean plane geometry, a quadrilateral is a polygon with four sides and four vertices or corners. Sometimes, the term quadrangle is used, by analogy with triangle, and sometimes tetragon for consistency with pentagon , hexagon and so on...
, is a pseudotriangle.
The convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
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 2n − 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 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.
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
Bitangent
In mathematics, a bitangent to a curve C is a line L that touches C in two distinct points P and Q and that has the same direction to C at these points...
line segment could be added between two vertices of the face.
A pointed pseudotriangulation with v vertices must have exactly 2v − 3 edges. This follows by a simple double counting
Double counting (proof technique)
In combinatorics, double counting, also called counting in two ways, is a combinatorial proof technique for showing that two expressions are equal by demonstrating that they are two ways of counting the size of one set...
argument involving the Euler characteristic
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent...
: 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.
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 graph
Laman graph
In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on n vertices such that, for all k, every k-vertex subgraph has at most 2k −3 edges, and such that the whole graph...
s: 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
Antimatroid
In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included...
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
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of the set, must have at least Ch−2×3n−h different pointed pseudotriangulations, where Ci denotes the ith Catalan number
Catalan number
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involvingrecursively defined objects...
. 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.