CON2VERT - constraints to vertices
Updated 11 Jul 2005
CON2VERT - convert a convex set of constraint inequalities into the set of vertices at the intersections of those inequalities;i.e., solve the "vertex enumeration" problem.
V = con2vert(A,b)
Converts the polytope (convex polygon, polyhedron, etc.) defined by the system of inequalities A*x <= b into a list of vertices V. Each ROW of V is a vertex. For n variables:
A = m x n matrix, where m >= n (m constraints, n variables)
b = m x 1 vector (m constraints)
V = p x n matrix (p vertices, n variables)
(1) This program emplyes a primal-dual polytope method.
(2) In dimensions higher than 2, duplicate vertices can appear using this method. This program detects duplicates at up to twelve digits of precision, then returns the unique vertices.
(3) Non-bounding constraints give erroneous results; therefore, the program detects non-bounding constraints and returns an error. You may wish to implement large "box" constraints on your variables if you need to induce bounding. For example, if x is a person's height in feet, the box constraint
-1 <= x <= 1000 would be a reasonable choice to induce boundedness, since no possible solution for x would be prohibited by the bounding box.
(4) This program requires that the feasible region have some finite extent in all dimensions. For example, the feasible region cannot be a line segment in 2-D space, or a plane in 3-D space.
(5) At least two dimensions are required.
(6) See companion function VERT2CON.
(7) Numerous examples are provided.
(8) ver 1.0: initial version, June 2005
(9) ver 1.1: enhanced redundancy checks, July 2005
(10) Written by Michael Kleder
Michael Kleder (2023). CON2VERT - constraints to vertices (https://www.mathworks.com/matlabcentral/fileexchange/7894-con2vert-constraints-to-vertices), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform CompatibilityWindows macOS Linux
Inspired: Analyze N-dimensional Convex Polyhedra, Ellipsoid Method, CON2VERT - constraints to vertices, updated
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!
Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.