Vertex enumeration problem
- Vertex enumeration problem
In mathematics, the vertex enumeration problem for a polyhedron, a polyhedral cell complex, a hyperplane arrangement, or some other object of discrete geometry, is the problem of determination of the object's vertices given some formal representation of the object. A classical example is the problem of enumeration of the vertices of a convex polyhedron specified by a set of linear inequalities: [Eric W. Weisstein "CRC Concise Encyclopedia of Mathematic," 2002,ISBN 1584883472, p. 3154, article "vertex enumeration"] :
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.
Computational complexity
The computational complexity of the problem is a subject of research in computer science.
A 1992 article by D. Avis and K. Fukuda [ [http://www.springerlink.com/content/m7440v7p3440757u/ David Avis and Komei Fukuda, "A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra"] , "Discrete and Computational Geometry", Volume 8, Number 1 / December, 1992, 295-313, doi|10.1007/BF02293050] presents the algorithm which finds the "v" vertices of a polyhedron defined by a nondegenerate system of "n" inequalities in "d" dimensions (or, dually, the "v" facets of the convex hull of "n" points in "d" dimensions, where each facet contains exactly "d" given points) in time O("ndv") and O("nd") space. The "v" vertices in a simple arrangement of "n" hyperplanes in "d" dimensions can be found in O("n"2"dv") time and O("nd") space complexity.
References
Wikimedia Foundation.
2010.
Look at other dictionaries:
Feedback vertex set — In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph.… … Wikipedia
Ménage problem — A table with ten place settings. According to the solution to the ménage problem, there are 3120 different ways in which five couples can choose seats at this table in such a way that men and women alternate and do not sit next to their partners … Wikipedia
Convex polytope — A 3 dimensional convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n dimensional space Rn.[1] Some authors use the terms convex polytope and convex… … Wikipedia
List of mathematics articles (V) — NOTOC Vac Vacuous truth Vague topology Valence of average numbers Valentin Vornicu Validity (statistics) Valuation (algebra) Valuation (logic) Valuation (mathematics) Valuation (measure theory) Valuation of options Valuation ring Valuative… … Wikipedia
David Avis — in 1987 Born March 20, 1951 (1951 03 20 … Wikipedia
Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i … Wikipedia
Criss-cross algorithm — This article is about an algorithm for mathematical optimization. For the naming of chemicals, see crisscross method. The criss cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional… … Wikipedia
2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… … Wikipedia
Series-parallel graph — In graph theory, series parallel graphs are graphs with two distinguished vertices called terminals , formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.Definition and… … Wikipedia
