|
Convex Polytopes
''Convex Polytopes'' is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perles, and G. C. Shephard, and published in 1967 by John Wiley & Sons. It went out of print in 1970. A second edition, prepared with the assistance of Volker Kaibel, Victor Klee, and Günter M. Ziegler, was published by Springer-Verlag in 2003, as volume 221 of their book series Graduate Texts in Mathematics. ''Convex Polytopes'' was the winner of the 2005 Leroy P. Steele Prize for mathematical exposition, given by the American Mathematical Society. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries. Topics The book has 19 chapters. After two chapters introducing background material in linear algebra, topology, and convex geometry, two more chapters ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others''Mathematical Programming'', by Melvyn W. Jeter (1986) p. 68/ref> (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. Yet other texts identify a convex polytope with its boundary. Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming. In the influential textbooks of Grünbaum and Ziegler on the subject, as well as in many other texts in discrete geometry, convex polytopes are often simply called "polytopes". Grünbaum points out that this is solely to avoi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gale Diagram
In the mathematical discipline of polyhedral combinatorics, the Gale transform turns the vertices of any convex polytope into a set of vectors or points in a space of a different dimension, the Gale diagram of the polytope. It can be used to describe high-dimensional polytopes with few vertices, by transforming them into sets of points in a space of a much lower dimension. The process can also be reversed, to construct polytopes with desired properties from their Gale diagrams. The Gale transform and Gale diagram are named after David Gale, who introduced these methods in a 1956 paper on neighborly polytopes. Definitions Transform Given a d-dimensional polytope, with n vertices, adjoin 1 to the Cartesian coordinates of each vertex, to obtain a (d+1)-dimensional column vector. The matrix A of these n column vectors has dimensions (d+1)\times n and rank d+1. The Gale transform replaces this matrix by a matrix B of dimension n\times (n-d-1), whose column vectors are a basis for the ke ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hirsch Conjecture
In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an ''n''-facet polytope in ''d''-dimensional Euclidean space has diameter no more than ''n'' − ''d''. That is, any two vertices of the polytope must be connected to each other by a path of length at most ''n'' − ''d''. The conjecture was first put forth in a letter by to George B. Dantzig in 1957 and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method. The conjecture is now known to be false in general. The Hirsch conjecture was proven for ''d'' d, then P' violates the ''d''-step conjecture. Santos then proceeds to construct a 5-dimensional spindle with length 6, hence proving that there exists another spindle that serves as a counterexample to the Hirsch conjecture. The first of these two spindles has 4 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Shortest Path Problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment. Definition The shortest path problem can be defined for graphs whether undirected, directed, or mixed. It is defined here for undirected graphs; for directed graphs the definition of path requires that consecutive vertices be connected by an appropriate directed edge. Two vertices are adjacent when they are both incident to a common edge. A path in an undirected graph is a sequence of vertices P = ( v_1, v_2, \ldots, v_n ) \in V \times V \times \cdots \times V such that v_i is adjacent to v_ for 1 \leq i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Blaschke Addition
In convex geometry and the geometry of convex polytopes, the Blaschke sum of two polytopes is a polytope that has a Facet (geometry), facet parallel to each facet of the two given polytopes, with the same Measure (mathematics), measure. When both polytopes have parallel facets, the measure of the corresponding facet in the Blaschke sum is the sum of the measures from the two given polytopes. Blaschke sums exist and are unique up to Translation (geometry), translation, as can be proven using the theory of the Minkowski problem for polytopes. They can be used to decompose arbitrary polytopes into simplex, simplices, and central symmetry, centrally symmetric polytopes into Parallelohedron#Parallelotope, parallelotopes. Although Blaschke sums of polytopes are used implicitly in the work of Hermann Minkowski, Blaschke sums are named for Wilhelm Blaschke, who defined a corresponding operation for smooth convex sets. The Blaschke sum operation can be extended to arbitrary convex bodies, g ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minkowski Addition
In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set : A + B = \. Analogously, the Minkowski difference (or geometric difference) is defined using the complement operation as : A - B = \left(A^c + (-B)\right)^c In general A - B \ne A + (-B). For instance, in a one-dimensional case A = 2, 2/math> and B = 1, 1/math> the Minkowski difference A - B = 1, 1/math>, whereas A + (-B) = A + B = 3, 3 In a two-dimensional case, Minkowski difference is closely related to erosion (morphology) in image processing. The concept is named for Hermann Minkowski. Example For example, if we have two sets ''A'' and ''B'', each consisting of three position vectors (informally, three points), representing the vertices of two triangles in \mathbb^2, with coordinates :A = \ and :B = \ then their Minkowski sum is :A + B = \ which comp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Circumscribed Sphere
In geometry, a circumscribed sphere of a polyhedron is a sphere that contains the polyhedron and touches each of the polyhedron's vertices. The word circumsphere is sometimes used to mean the same thing, by analogy with the term ''circumcircle''. As in the case of two-dimensional circumscribed circles (circumcircles), the radius of a sphere circumscribed around a polyhedron is called the circumradius of , and the center point of this sphere is called the circumcenter of . Existence and optimality When it exists, a circumscribed sphere need not be the smallest sphere containing the polyhedron; for instance, the tetrahedron formed by a vertex of a cube and its three neighbors has the same circumsphere as the cube itself, but can be contained within a smaller sphere having the three neighboring vertices on its equator. However, the smallest sphere containing a given polyhedron is always the circumsphere of the convex hull of a subset of the vertices of the polyhedron.. In ''De s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Inscribed Sphere
In geometry, the inscribed sphere or insphere of a convex polyhedron is a sphere that is contained within the polyhedron and tangent to each of the polyhedron's faces. It is the largest sphere that is contained wholly within the polyhedron, and is dual to the dual polyhedron's circumsphere. The radius of the sphere inscribed in a polyhedron ''P'' is called the inradius of ''P''. Interpretations All regular polyhedra have inscribed spheres, but most irregular polyhedra do not have all facets tangent to a common sphere, although it is still possible to define the largest contained sphere for such shapes. For such cases, the notion of an insphere does not seem to have been properly defined and various interpretations of an ''insphere'' are to be found: * The sphere tangent to all faces (if one exists). * The sphere tangent to all face planes (if one exists). * The sphere tangent to a given set of faces (if one exists). * The largest sphere that can fit inside the polyhedron. Often ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Eberhard's Theorem
In mathematics, and more particularly in polyhedral combinatorics, Eberhard's theorem partially characterizes the multisets of polygons that can form the faces of simple convex polyhedra. It states that, for given numbers of triangles, quadrilaterals, pentagons, heptagons, and other polygons other than hexagons, there exists a convex polyhedron with those given numbers of faces of each type (and an unspecified number of hexagonal faces) if and only if those numbers of polygons obey a linear equation derived from Euler's polyhedral formula. The theorem is named after Victor Eberhard, a blind German mathematician, who published it in 1888 in his habilitation thesis and in expanded form in an 1891 book on polyhedra. Definitions and statement For an arbitrary convex polyhedron, one can define numbers p_3, p_4, p_5, etc., where p_i counts the faces of the polyhedron that have exactly i sides. A three-dimensional convex polyhedron is defined to be simple when every vertex of the polyhedr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Steinitz's Theorem
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. This result provides a classification theorem for the three-dimensional convex polyhedra, something that is not known in higher dimensions. It provides a complete and purely combinatorial description of the graphs of these polyhedra, allowing other results on them, such as Eberhard's theorem on the realization of polyhedra with given types of faces, to be proven more easily, without reference to the geometry of these shapes. Additionally, it has been applied in graph drawing, as a way to construct ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
N-skeleton
In mathematics, particularly in algebraic topology, the of a topological space presented as a simplicial complex (resp. CW complex) refers to the subspace that is the union of the simplices of (resp. cells of ) of dimensions In other words, given an inductive definition of a complex, the is obtained by stopping at the . These subspaces increase with . The is a discrete space, and the a topological graph. The skeletons of a space are used in obstruction theory, to construct spectral sequences by means of filtrations, and generally to make inductive arguments. They are particularly important when has infinite dimension, in the sense that the do not become constant as In geometry In geometry, a of P (functionally represented as skel''k''(''P'')) consists of all elements of dimension up to ''k''. For example: : skel0(cube) = 8 vertices : skel1(cube) = 8 vertices, 12 edges : skel2(cube) = 8 vertices, 12 edges, 6 square faces For simplicial sets The above def ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Extremal Combinatorics
Extremal combinatorics is a field of combinatorics, which is itself a part of mathematics. Extremal combinatorics studies how large or how small a collection of finite objects (numbers, graphs, vectors, sets, etc.) can be, if it has to satisfy certain restrictions. Much of extremal combinatorics concerns classes of sets; this is called extremal set theory. For instance, in an ''n''-element set, what is the largest number of ''k''-element subsets that can pairwise intersect one another? What is the largest number of subsets of which none contains any other? The latter question is answered by Sperner's theorem, which gave rise to much of extremal set theory. Another kind of example: How many people can be invited to a party where among each three people there are two who know each other and two who don't know each other? Ramsey theory shows that at most five persons can attend such a party. Or, suppose we are given a finite set of nonzero integers, and are asked to mark as la ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
