2
$\begingroup$

We have a convex polytope $P$ for which we know its set of vertices. Using this set we characterize the H-representation of $P$ as: $\mathbf{A}\mathbf{x} < \mathbf{b}$.
If a hyperplane defined by the equation $\mathbf{c}.\mathbf{x}-d=0$ cuts the polytope in two. How we can characterize (i.e. find the H-representation or V-representation) the two resulting polytopes?

'I asked this question on Mathoverflow but it was put on hold because they claim it's off-topic. They recommended me to ask it here'.

$\endgroup$
5
$\begingroup$

If you know both the $V$ and $H$ representations of your original polytope, then each of the two polytopes have vertices given by the original vertices that are all on one side of the hyperplane (i.e. $c \cdot x \leq d$ or $c \cdot x \geq d$), combined with the new vertices given by the vertices of the solution to the combined equations/inequalities $c \cdot x = d$ and $Ax \leq b$.

The $H$ representations are even easier: either $c \cdot x \leq d$ or $c \cdot x \geq d$, combined with $Ax \leq b$.

UPDATE: Per your comment request, I'll review what I know about efficiently getting H-representation from V-representation and vice-versa. First of all, the problem of computing H-representation of a convex hull of a given set of vertices, and computing vertices of a given H-representation are equivalent. To see this, given a set of vertices where you want the H-representation of the convex hull, consider the "dual polytope" defined by the inequalities $v_i \cdot x \leq 1$ where $v_i$ are your original vertices and $x$ are the variables. Then vertices of this dual polytope correspond to normal vectors of facets of the original polytope (full-dimensional faces, defined by a single inequality $x \cdot v \leq 1$ for the H-representation (where $x$ is the normal vector)). Thus if you can find all vertices of the dual polytope then you know a minimal H-representation of the original polytope. To make this work you need to translate your original vertices so that $0$ is in the interior of the original polytope (covex hull), which is easy e.g. if you compute the average of all original vertices and subtract this from all original vertices before forming the dual.

So it all boils down to finding all the vertices of a polytope given in H-representation. There are at least two efficient (well, efficient under their own assumptions) ways to do this.

If the dimension of the polytope is low (e.g. especially dimension 2 or 3 or 4), then probably the best way is to use the so-called beneath-beyond algorithm which you can read about e.g. in the computational geometry book by Edelsbrunner, or perhaps online. It basically maintains the facets (full-dimensional faces) of the convex hull of all vertices found so far, and then for each outer pointing perpendicular vector (normal vector) to a facet, uses linear programming to maximize the dot-product with this vector, over the original H-representation, and either find a new vertex or confirm that the normal vector for the facet defines a true facet of the convex hull, so it doesn't need to be tested anymore. When a new vertex is found, you find the "horizon" of current facets that share the boundary of the exterior of the existing convex hull that can see this new vertex, and extend the one-dimensional-lower faces on the boundary of these facets that contain these vertices to new facets, by adding the new vertex to them, thus updating the convex hull and adding new facets whose normal vectors need to be tested to find more vertices. Eventually no new vertices will be found and then you are done. In low-dimensions, Raymond Seidel's expected linear time linear programming in fixed dimension is the way to go, although the hidden "fixed" constants in fixed dimension for the expected running are exponential in the dimension, so probably only good for dimension around 5 or less. Seidel's algorithm is described in the computational geometry book by Overmars and coauthors, and also probably available online.

Anyway, the other way which is good if the dimension is large is the so-called "compact, output sensitive polynomial time" algorithm by Avis and Fukuda. I don't think any books have this but papers are available online. The idea is that you only maintain vertices and edges of the polytope you are constructing, which has quadratic complexity in terms of the total number of vertices. and then you use polynomial time linear programming that is slower in low dimension than other approaches, but always polynomial time even if the dimension is not fixed (e.g., interior point methods) to repeatedly try to extend the set of known vertices along all possible edge directions, until all vertices are found. This is implemented at

http://library.wolfram.com/infocenter/MathSource/440/

but in low dimensions (especially dimensions 2-4), it probably won't run as fast as the first approach I described.

$\endgroup$
  • $\begingroup$ One last thing please: what are the most used (and efficient) algorithms to obtain the H-representation of a convex polytope from its V-representation and vice-versa? thank you! $\endgroup$ – tam Jun 4 '15 at 16:22
  • $\begingroup$ @mat I'll update my answer, I think it's a little too long to explain in a comment. $\endgroup$ – user2566092 Jun 4 '15 at 16:39
  • $\begingroup$ @mat OK updated, you'll have to do a little hunting online or in library books to fill in the rest of the details I left out but hopefully this is enough to make it possible. Also, if you want to do the beneath-beyond algorithm efficiently, I have code for that as long as your polytope is full-dimensional and you have a linear programming solver that will suffice as a "vertex finding oracle that finds a vertex that maximizes a given linear functional" that you can plug in through file input/output protocols that I made for passing objectives/solutions and a given system call for the optimizer. $\endgroup$ – user2566092 Jun 4 '15 at 17:31
  • $\begingroup$ I don't need the code for the moment. Thank you! $\endgroup$ – tam Jun 4 '15 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.