| Description |
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)
NOTES:
(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 |
