In geometry, the two ears theorem states that every simple polygon with more than three vertices has at least two ears, vertices that can be removed from the polygon without introducing any crossings. The two ears theorem is equivalent to the existence of polygon triangulations. It is frequently attributed to Gary H. Meisters, but was proved earlier by Max Dehn.
A simple polygon is a simple closed curve in the Euclidean plane consisting of finitely many line segments in a cyclic sequence, with each two consecutive line segments meeting at a common endpoint, and no other intersections. By the Jordan curve theorem, it separates the plane into two regions, one of which (the interior of the polygon) is bounded. An ear of a polygon is defined as a triangle formed by three consecutive vertices of the polygon, such that its edge lies entirely in the interior of the polygon. The two ears theorem states that every simple polygon that is not itself a triangle has at least two ears. [1]
An ear and its two neighbors form a triangle within the polygon that is not crossed by any other part of the polygon. Removing a triangle of this type produces a polygon with fewer sides, and repeatedly removing ears allows any simple polygon to be triangulated. Conversely, if a polygon is triangulated, the weak dual of the triangulation (a graph with one vertex per triangle and one edge per pair of adjacent triangles) will be a tree and each leaf of the tree will form an ear. Since every tree with more than one vertex has at least two leaves, every triangulated polygon with more than one triangle has at least two ears. Thus, the two ears theorem is equivalent to the fact that every simple polygon has a triangulation. [2]
Triangulation algorithms based on this principle have been called ear-clipping algorithms. Although a naive implementation is slow, ear-clipping can be sped up by the observation that a triple of consecutive vertices of a polygon forms an ear if and only if the central vertex of the triple is convex and the triple forms a triangle that does not contain any reflex vertices. By maintaining a queue of triples with this property, and repeatedly removing an ear from the queue and updating the adjacent triples, it is possible to perform ear-clipping in time , where is the number of input vertices and is the number of reflex vertices. [3]
If a simple polygon is triangulated, then a triple of consecutive vertices forms an ear if is a convex vertex and none of its other neighbors in the triangulation lie in triangle . By testing all neighbors of all vertices, it is possible to find all the ears of a triangulated simple polygon in linear time. [4] Alternatively, it is also possible to find a single ear of a simple polygon in linear time, without triangulating the polygon. [5]
An ear is called exposed when its central vertex belongs to the convex hull of the polygon. However, it is possible for a polygon to have no exposed ears. [6]
Ears are a special case of a principal vertex, a vertex such that the line segment connecting the vertex's neighbors does not cross the polygon or touch any other vertex of it. A principal vertex for which this line segment lies outside the polygon is called a mouth. Analogously to the two ears theorem, every non-convex simple polygon has at least one mouth. Polygons with the minimum number of principal vertices of both types, two ears and a mouth, are called anthropomorphic polygons. [7] Repeatedly finding and removing a mouth from a non-convex polygon will eventually turn it into the convex hull of the initial polygon. This principle can be applied to the surrounding polygons of a set of points; these are polygons that use some of the points as vertices, and contain the rest of them. Removing a mouth from a surrounding polygon produces another surrounding polygon, and the family of all surrounding polygons can be found by reversing this mouth-removal process, starting from the convex hull. [8]
The two ears theorem is often attributed to a 1975 paper by Gary H. Meisters, from which the "ear" terminology originated. [1] However, the theorem was proved earlier by Max Dehn (circa 1899) as part of a proof of the Jordan curve theorem. To prove the theorem, Dehn observes that every polygon has at least three convex vertices. If one of these vertices, v, is not an ear, then it can be connected by a diagonal to another vertex x inside the triangle uvw formed by v and its two neighbors; x can be chosen to be the vertex within this triangle that is farthest from line uw. This diagonal decomposes the polygon into two smaller polygons, and repeated decomposition by ears and diagonals eventually produces a triangulation of the whole polygon, from which an ear can be found as a leaf of the dual tree. [9]
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph, or a planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
A triangle is a polygon with three corners and three sides, one of the basic shapes in geometry. The corners, also called vertices, are zero-dimensional points while the sides connecting them, also called edges, are one-dimensional line segments. A triangle has three internal angles, each one bounded by a pair of adjacent edges; the sum of angles of a triangle always equals a straight angle. The triangle is a plane figure and its interior is a planar region. Sometimes an arbitrary edge is chosen to be the base, in which case the opposite vertex is called the apex; the shortest segment between base and apex is the height. The area of a triangle equals one-half the product of height and base length.
In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring of a triangulation of an -dimensional simplex contains a cell whose vertices all have different colors.
In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a simple polygon. Equivalently, a polygon is convex if every line that does not contain any edge intersects the polygon in at most two points.
In computational geometry, polygon triangulation is the partition 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.
In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.
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 the following real-world problem:
"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"
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 π.
In geometry, a vertex is a point where two or more curves, lines, or edges meet or intersect. As a consequence of this definition, the point where two lines meet to form an angle and the corners of polygons and polyhedra are vertices.
In geometry, an anthropomorphic polygon is a simple polygon with precisely two ears and one mouth. That is, for exactly three polygon vertices, the line segment connecting the two neighbors of the vertex does not cross the polygon. For two of these vertices the line segment connecting the neighbors forms a diagonal of the polygon, contained within the polygon. For the third vertex the line segment connecting the neighbors lies outside the polygon, forming the entrance to a concavity of the polygon.
In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.
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 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.
In geometry, a Schönhardt polyhedron is a polyhedron with the same combinatorial structure as a regular octahedron, but with dihedral angles that are non-convex along three disjoint edges. Because it has no interior diagonals, it cannot be triangulated into tetrahedra without adding new vertices. It has the fewest vertices of any polyhedron that cannot be triangulated. It is named after the German mathematician Erich Schönhardt, who described it in 1928, although the artist Karlis Johansons had exhibited a related structure in 1921.
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.
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, 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.
In computational geometry, a fan triangulation is a simple way to triangulate a polygon by choosing a vertex and drawing edges to all of the other vertices of the polygon. Not every polygon can be triangulated this way, so this method is usually only used for convex polygons.
In discrete geometry and computational geometry, the relative convex hull or geodesic convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.
In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.
Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be generated in polynomial time per object, using only enough memory to store a constant number of objects. They work by organizing the objects to be generated into a spanning tree of their state space, and then performing a depth-first search of this tree.
