Pseudotriangle

Last updated
The pseudotriangle between three smooth convex sets (left), and a polygonal pseudotriangle (right). Pseudotriangles.svg
The pseudotriangle between three smooth convex sets (left), and a polygonal pseudotriangle (right).

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. 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 π.

Contents

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 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 [2] and for dynamic graph drawing and shape morphing. [3] Pointed pseudotriangulations arise in rigidity theory as examples of minimally rigid planar graphs, [4] and in methods for placing guards in connection with the art gallery theorem. [5] The shelling antimatroid of 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, and Streinu (2008).

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. 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

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. [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

A shelling sequence of a planar point set and the pointed pseudotriangulation derived from this sequence. Convex shelling.svg
A shelling sequence of a planar point set and the pointed pseudotriangulation derived from this sequence.

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 2v − 3 edges. [8] 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. [9]

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. [6] 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 Ch−2×3n−h different pointed pseudotriangulations, where Ci 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. [10]

See also

Notes

  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, JSTOR   1970286, MR   0124917 . 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, MR   0447029 .
  2. ↑ Agarwal et al. (2002).
  3. ↑ Streinu (2006).
  4. ↑ Haas et al. (2005)
  5. ↑ Speckmann and Tóth (2005).
  6. 1 2 Har-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).

Related Research Articles

Delaunay triangulation Triangulation method named after Boris Delaunay

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

Polygon triangulation

In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

Point-set triangulation

A triangulation of a set of points in the Euclidean space is a simplicial complex that covers the convex hull of , and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards who together can observe the whole gallery. In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon.

Dual graph

In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

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 related problem is to show that any non-self-crossing polygonal chain can be straightened, again by a continuous transformation that preserves edge distances and avoids crossings.

Geometric graph theory

Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices, thus it is "the theory of geometric and topological graphs". Geometric graphs are called in recent years very often spatial networks.

Straight skeleton Method in geometry for representing a polygon by a topological skeleton

In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves. However, both are homotopy-equivalent to the underlying polygon.

Moser spindle Undirected unit-distance graph requiring four colors

In graph theory, a branch of mathematics, the Moser spindle is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It is a unit distance graph requiring four colors in any graph coloring, and its existence can be used to prove that the chromatic number of the plane is at least four.

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 has exactly 2n − 3 edges. Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures. This characterization, however, had already been discovered in 1927 by Hilda Geiringer.

Circle packing theorem Describes the possible tangency relations between circles with disjoint interiors

The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph:

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the (simple) 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs. Branko Grünbaum has called this theorem "the most important and deepest known result on 3-polytopes."

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

The Alexandrov uniqueness theorem is a rigidity theorem in mathematics, describing three-dimensional convex polyhedra in terms of the distances between points on their surfaces. It implies that convex polyhedra with distinct shapes from each other also have distinct metric spaces of surface distances, and it characterizes the metric spaces that come from the surface distances on polyhedra. It is named after Soviet mathematician Aleksandr Danilovich Aleksandrov, who published it in the 1940s.

Apollonian network

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

Ileana Streinu Romanian-American computer scientist and mathematician

Ileana Streinu is a Romanian-American computer scientist and mathematician, the Charles N. Clark Professor of Computer Science and Mathematics at Smith College in Massachusetts. She is known for her research in computational geometry, and in particular for her work on kinematics and structural rigidity.

In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple 3-vertex-connected planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by W. T. Tutte (1963), states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex. It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.

A covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covering. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

Ideal polyhedron Type of polyhedron

In three-dimensional hyperbolic geometry, an ideal polyhedron is a convex polyhedron all of whose vertices are ideal points, points "at infinity" rather than interior to three-dimensional hyperbolic space. It can be defined as the convex hull of a finite set of ideal points. An ideal polyhedron has ideal polygons as its faces, meeting along lines of the hyperbolic space.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.