A convex polytope is a special case of a polytope In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions . Some theories further generalise the idea to include such things as unbounded polytopes (apeirotopes and, having the additional property that it is also a 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. For example, a solid cube is convex, but anything that is hollow or has a dent in it, for example, a crescent shape, is not convex of points in the n-dimensional space Rn.[1] Some authors use the terms "convex polytope" and "convex polyhedron" interchangeably, while others prefer to draw a distinction between the notions of a polyhedron A polyhedron is a geometric solid in three dimensions with flat faces and straight edges. The word polyhedron comes from the Classical Greek πολύεδρον, as poly- (stem of πολύς, "many") + -edron (form of έδρα, "base", "seat", or "face") and a polytope.
In addition, some texts require a polytope to be a bounded set In mathematical analysis and related areas of mathematics, a set is called bounded, if it is, in a certain sense, of finite size. Conversely a set which is not bounded is called unbounded, while others[2] (including this article) allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue.
Convex polytopes play an important role both in various branches of mathematics Mathematics is the study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions and in applied areas, most notably in linear programming Linear programming is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear equations.
A comprehensive and influential book in the subject, called Convex Polytopes, was published in 1967 by Branko Grünbaum Branko Grünbaum is a Croatian-born mathematician and a professor emeritus at the University of Washington in Seattle. He received his Ph.D. in 1957 from Hebrew University of Jerusalem in Israel. He has authored over 200 papers, mostly in discrete geometry, an area in which he is particularly well known for various meticulous classification. In 2003 the 2nd edition of the book was published, with significant additional material contributed by new writers.[1]
In Grünbaum's book, and in some other texts in discrete geometry Discrete geometry or combinatorial geometry may be loosely defined as study of geometrical objects and properties that are discrete or combinatorial, either by their nature or by their representation; the study that does not essentially rely on the notion of continuity, convex polytopes are often simply called "polytopes". Grünbaum points out that this is solely to avoid the endless repetition of the word "convex", and that the discussion should throughout be understood as applying only to the convex variety.
A polytope is called full-dimensional, if it is an n-dimensional object in Rn.
Contents |
Examples
- Many examples of bounded convex polytopes can be found in the article "polyhedron A polyhedron is a geometric solid in three dimensions with flat faces and straight edges. The word polyhedron comes from the Classical Greek πολύεδρον, as poly- (stem of πολύς, "many") + -edron (form of έδρα, "base", "seat", or "face")".
- In the 2-dimensional case the full-dimensional examples are a half-plane In geometry, a half-space is either of the two parts into which a plane divides the three-dimensional euclidean space. More generally, a half-space is either of the two parts into which a hyperplane divides an affine space. That is, the points that are not incident to the hyperplane are partitioned into two convex sets , such that any subspace, a strip between two parallel lines, an angle In geometry, an angle is the figure formed by two rays sharing a common endpoint, called the vertex of the angle. The magnitude of the angle is the "amount of rotation" that separates the two rays, and can be measured by considering the length of circular arc swept out when one ray is rotated about the vertex to coincide with the other shape (the intersection of two non-parallel half-planes), a shape defined by a convex polygonal chain with two rays attached to its ends, and a convex polygon A convex polygon is a simple polygon whose interior is a convex set. The following properties of a simple polygon are all equivalent to convexity:.
- Special cases of an unbounded convex polytope are a slab between two parallel hyperplanes, a wedge defined by two non-parallel half-spaces, a polyhedral cylinder (infinite prism In geometry, an n-sided prism is a polyhedron made of an n-sided polygonal base, a translated copy, and n faces joining corresponding sides. Thus these joining faces are parallelograms. All cross-sections parallel to the base faces are the same. A prism is a subclass of the prismatoids), and a polyhedral cone (infinite prism In geometry, an n-sided prism is a polyhedron made of an n-sided polygonal base, a translated copy, and n faces joining corresponding sides. Thus these joining faces are parallelograms. All cross-sections parallel to the base faces are the same. A prism is a subclass of the prismatoids), defined by three or more half-spaces passing through a common point.
Definitions
A convex polytope may be defined in a number of ways, depending on what is more suitable for the problem at hand. Grünbaum's definition is in terms of a convex set of points in space. Other important definitions are; as the intersection In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements of half-spaces (half-space representation), as the 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 a set of points (vertex representation).
Vertex representation (Convex hull)
In his book Convex polytopes, Grünbaum defines a convex polytope as a compact convex set:
- A set (where R is real space) is convex if, for each pair of distinct points , the closed segment with endpoints a and b is contained within K.
- A compact convex set is a polytope provided ext K is a finite set.
This is equivalent to defining a finite convex polytope as the 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 a finite set of points, where the finite set must contain the set of extreme points of the polytope. Such a definition is called a vertex representation (V-representation or V-description).[1] There exist infinitely many V-descriptions of a convex polytope. However, for a full-dimensional convex polytope, the minimal V-description is in fact unique and is given by the set of the vertices In geometry, a vertex is a special kind of point which describes the corners or intersections of geometric shapes. Vertices are commonly used in computer graphics to define the corners of surfaces (typically triangles) in 3D models, where each such point is given as a vector of the polytope.[1]
Intersection of half-spaces
A convex polytope may be defined as an intersection of a finite number of half-spaces. Such definition is called a half-space representation (H-representation or H-description).[1] There exist infinitely many H-descriptions of a convex polytope. However, for a full-dimensional convex polytope, the minimal H-description is in fact unique and is given by the set of the facet-defining halfspaces.[1]
A closed half-space can be written as a linear inequality The set of solutions of a system of linear inequalities corresponds to the intersection of the half-planes defined by individual inequalities. It is a convex set, since the half-planes are convex sets, and the intersection of a set of convex sets is also convex. In the non-degenerate cases this convex set if a convex polyhedron . It may also be:[1]
where n is the dimension of the space containing the polytope under consideration. Hence, a closed convex polytope may be regarded as the set of solutions to the system of linear inequalities:
where m is the number of half-spaces defining the polytope. This can be concisely written as the matrix An item in a matrix is called an entry or an element. The example has entries 1, 9, 13, 20, 55, and 4. Entries are often denoted by a variable with two subscripts, as shown on the right. Matrices of the same size can be added and subtracted entrywise and matrices of compatible sizes can be multiplied. These operations have many of the properties inequality:
where A is an m×n matrix, x is an n×1 column vector of variables, and b is an m×1 column vector of constants.
An open convex polytope is defined in the same way, with strict inequalities used in the formulas instead of the non-strict ones.
The coefficients of each row of A and b correspond with the coefficients of the linear inequality defining the respective half-space. Hence, each row in the matrix corresponds with a supporting hyperplane of the polytope, a hyperplane bounding a half-space that contains the polytope. If a supporting hyperplane also intersects the polytope, it is called a bounding hyperplane (since it is a supporting hyperplane, it can only intersect the polytope at the polytope's boundary).
The foregoing definition assumes that the polytope is full-dimensional. If it is not, then the solution of Ax ≤ b lies in a proper affine subspace of Rn and discussion of the polytope may be constrained to this subspace.
In general the intersection of arbitrary half-spaces need not be bounded. However if one wishes to have a definition equivalent to that as a convex hull, then bounding must be explicitly required.
Finite basis theorem
The finite basis theorem[2] is an extension of the notion of V-description to include infinite polytopes. The theorem states that a convex polyhedron is the convex sum of its vertices plus the conical sum of the direction vectors of its infinite edges.
Properties
Every (bounded) complex polytope is the image of a simplex In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron, and a 4-simplex is a pentachoron. A single point may be, as every point is a convex combination of the (finitely many) vertices. However, polytopes are not in general isomorphic to simplices. This is in contrast to the case of vector spaces A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex numbers, rational numbers, or even more general fields and linear combinations In mathematics, linear combinations is a concept central to linear algebra and related fields of mathematics. Most of this article deals with linear combinations in the context of a vector space over a field, with some generalizations given at the end of the article, every finite dimensional vector space being not only an image of, but in fact isomorphic to, Euclidean space of some dimension (or analog over other fields).
The face lattice
Given a convex polytope P defined by the matrix inequality , if each row in A corresponds with a bounding hyperplane and is linearly independent of the other rows, then each facet of P corresponds with exactly one row of A, and vice versa. Each point on a given facet will satisfy the linear equality of the corresponding row in the matrix. (It may or may not also satisfy equality in other rows). Similarly, each point on a ridge will satisfy equality in two of the rows of A.
The face lattice of a square pyramid, drawn as a Hasse diagram In order theory, a branch of mathematics, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set (S, ≤) one represents each element of S as a vertex in the plane and draws a line segment or curve that goes; each face in the lattice is labeled by its vertex set.In general, an (n − j)-dimensional face satisfies equality in j specific rows of A. These rows form a basis of the face. Geometrically speaking, this means that the face is the set of points on the polytope that lie in the intersection of j of the polytope's bounding hyperplanes.
The faces of a convex polytope thus form a lattice In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum (the elements' least upper bound; called their join) and an infimum (greatest lower bound; called their meet). Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities. Since the two definitions are called its face lattice, where the partial ordering is by set containment of faces. To ensure that every pair of faces has a join and a meet in the face lattice, the polytope itself and the empty set are also considered 'faces'. The whole polytope is the unique maximum element of the lattice, and the empty set, considered to be a (−1)-dimensional face (a null polytope) of every polytope, is the unique minimum element of the lattice.
Two polytopes are called combinatorially isomorphic if their face lattices are isomorphic In abstract algebra, an isomorphism is a bijective map f such that both f and its inverse f −1 are homomorphisms, i.e., structure-preserving mappings. In the more general setting of category theory, an isomorphism is a morphism f: X → Y in a category for which there exists an "inverse" f −1: Y → X, with the property that both f .
The polytope graph (polytopal graph, graph of the polytope) is the set of vertices and edges of the polytope only - higher dimensional faces are ignored. In fact, for a simple polytope the face lattice is completely determined by its polytope graph (Blind & Mani-Levitska (1987), a simple proof by Kalai (1988))[3]. The latter fact is instrumental in the proof that from the point of view of computational complexity Computational complexity theory is a branch of the theory of computation in computer science that focuses on classifying computational problems according to their inherent difficulty. In this context, a computational problem is understood to be a task that is in principle amenable to being solved by a computer. Informally, a computational problem, the problem of deciding whether two convex polytopes are combinatorially isomorphic is equivalent to the graph isomorphism problem, even when restricted to the class of simple or simplicial polytopes. [4]
See also "Polyhedral graph".
Topological properties
All bounded convex polytopes in Rn, being topological (n − 1)-spheres In mathematics, an n-sphere is a generalization of the surface of an ordinary sphere to arbitrary dimension. For any natural number n, an n-sphere of radius r is defined as the set of points in -dimensional Euclidean space which are at distance r from a central point, where the radius r may be any positive real number. It is an n-dimensional, have a 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. It is commonly denoted by χ (Greek letter chi) of 0 for odd n and 2 for even n. Hence, they may be regarded as tessellations A tessellation or tiling of the plane is a collection of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art of M. C. Escher. Tessellations are seen of (n − 1)-dimensional elliptic space.
Simplicial decomposition
A convex polytope can be decomposed into a simplicial complex In mathematics, a simplicial complex is a topological space of a particular kind, constructed by "gluing together" points, line segments, triangles, and their n-dimensional counterparts . Simplicial complexes should not be confused with the more abstract notion of a simplicial set appearing in modern simplicial homotopy theory, or union of simplices In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron, and a 4-simplex is a pentachoron. A single point may be, satisfying certain properties.
Given a convex r-dimensional polytope P, a subset of its vertices containing (r+1) linearly independent points defines an r-simplex In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron, and a 4-simplex is a pentachoron. A single point may be. It is possible to form a collection of subsets such that the union of the corresponding simplices is equal to P, and the intersection of any two simplices is either empty or a lower-dimensional simplex.
Algorithmic problems for a convex polytope
Construction of representations
Different representations of a convex polytope have different utility, therefore the construction of one representation given another one is an important problem. The problem of the construction of a V-representation is known as the vertex enumeration problem and the problem of the construction of a H-representation is known as the facet enumeration problem. While the vertex set of a bounded convex polytope uniquely defines it, in various applications it is important to know more about the combinatorial structure of the polytope, i.e., about its face lattice. Various convex hull algorithms deal both with the facet enumeration and face lattice construction.
In the planar case, i.e., for a convex polygon A convex polygon is a simple polygon whose interior is a convex set. The following properties of a simple polygon are all equivalent to convexity:, both facet and vertex enumeration problems amount to the ordering vertices (resp. edges) around the convex hull. It is a trivial task when the convex polygon is specified in a traditional for polygons In geometry a polygon is traditionally a plane figure that is bounded by a closed path or circuit, composed of a finite sequence of straight line segments (i.e., by a closed polygonal chain). These segments are called its edges or sides, and the points where two edges meet are the polygon's vertices or corners. An n-gon is a polygon with n sides way, i.e., by the ordered sequence of its vertices . When the input list of vertices (or edges) is unordered, the time complexity Computational complexity theory is a branch of the theory of computation in computer science that focuses on classifying computational problems according to their inherent difficulty. In this context, a computational problem is understood to be a task that is in principle amenable to being solved by a computer. Informally, a computational problem of the problems becomes O(m log m).[citation needed]
References
- ^ a b c d e f g Branko Grünbaum Branko Grünbaum is a Croatian-born mathematician and a professor emeritus at the University of Washington in Seattle. He received his Ph.D. in 1957 from Hebrew University of Jerusalem in Israel. He has authored over 200 papers, mostly in discrete geometry, an area in which he is particularly well known for various meticulous classification, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Gunter M. Ziegler, 2003, ISBN 0387404090, ISBN 978-0387404097, 466pp.
- ^ a b Mathematical Programming, by Melvyn W. Jeter (1986) ISBN 0824774787, p. 68
- ^ Lectures on Polytopes, by Günter M. Ziegler (1995) ISBN 038794365X
- ^ Volker Kaibel, Alexander Schwartz, "On the Complexity of Polytope Isomorphism Problems", Graphs and Combinatorics, 19 (2):215 —230, 2003.
External links
- Weisstein, Eric W. Eric W. Weisstein is an encyclopedist who created and maintains MathWorld and Eric Weisstein's World of Science (ScienceWorld). He currently works for Wolfram Research, Inc, "Convex polygon" from MathWorld MathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by Wolfram Research Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at Urbana–Champaign.
- Weisstein, Eric W. Eric W. Weisstein is an encyclopedist who created and maintains MathWorld and Eric Weisstein's World of Science (ScienceWorld). He currently works for Wolfram Research, Inc, "Convex polyhedron" from MathWorld MathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by Wolfram Research Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at Urbana–Champaign.
- Komei Fukuda, Polyhedral computation FAQ.
Categories: Polytopes In geometry, polytope means the generalization to any dimension of the sequence: polygon in two dimensions, polyhedron in three dimensions, and polychoron in four dimensions | Convex geometry
