Finding a hyperplane that splits a convex polytope evenly - MathOverflow

Finding a hyperplane that splits a convex polytope evenly

2011-09-07T18:18:06Z

Say we have a convex polytope in standard form:

\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\ \mathbf{x} \ge 0 \end{array} \end{equation*}

Are there any known methods for finding a hyperplane $\mathbf{d} \mathbf{x} +d_0= 0$ that splits the polyhedron in a way that the number of vertices on each side of the hyperplane is approximately the same? (i.e. a hyperplane that minimizes the absolute difference of vertex cardinalities on the two sides of the split).

Also, are there any known results regarding the computational complexity of this problem?

Addendum: Restricting the types of cuts:

Here is a variation of the original problem with the hope that it is easier to solve than the original one:

Is there a way to efficiently compute or estimate for which coordinate $i$ a hyperplane of the form $d_ix_i + d_0 = 0$ would yield the lowest absolute difference of vertex cardinalities on both sides of the split? By efficient I mean anything more efficient than the exhaustive enumeration of vertex cardinalities for all such possible splits.

Note:

I first asked this question in CSTheory.stackexchange.com last week. Since the question has not seen any significant progress since then, I thought I could try here.

Answer by Joseph O'Rourke for Finding a hyperplane that splits a convex polytope evenly

2011-09-07T18:57:47Z

If you have a generic direction $\mathbf{u}$ in your hands, then you can sweep a hyperplane orthogonal to $\mathbf{u}$ until it has $\lfloor n/2 \rfloor$ vertices of the $n$-vertex polytope to one side. The sweeping can be efficient: project the polytope vertices onto $\mathbf{u}$ and find the median. So the question reduces to finding a generic direction.

A random direction will be generic with high probability, so one approach is to generate random direction vectors, sweep, repeat until you are not unlucky.

Edit. As Kurt Luoto pointed out, I (inadvertently) assumed the vertices were available, neglecting that the polytope is given in "standard form." One could use the Avis and Fukuda pivoting algorithm, which could list the $n$ vertices in time $O(n d f)$, where $f$ the number of facets, and $d$ the dimension: "A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra," Discrete & Computational Geometry, Volume 8, Number 1, 295-313, 1992.

Offhand I do not see how to bisect the vertices without computing the vertices, but I would not rule it out...

Answer by Kurt Luoto for Finding a hyperplane that splits a convex polytope evenly

2011-09-07T19:07:09Z

It seems that Joseph's approach would require computing the set of vertices from the standard form. I don't recall what the complexity of this is in the worst case, but I dimly remember it being pretty bad in the extreme case. In any case, I wonder whether that is in the spirit of the original question.

Sad to say, I don't have an idea to propose.

Answer by Carl Feynman for Finding a hyperplane that splits a convex polytope evenly

2012-03-15T19:17:54Z

This is not an answer, it's a warning of a dead end.

I considered using a Markov Chain to randomly sample the vertices. Just start at an arbitrary vertex, and at each time step, pick an edge-connected neighbor of the current vertex and step to that vertex. The distribution of points hit by this chain converges to the uniform distribution on the vertices. So we could use it to take a random sample of vertices and pick a splitting plane for that sample. This would be an approximation to the real splitting plane. Unfortunately I was able to construct a polytope where the convergence takes time exponential in the number of constraints. So as long as you're taking exponential time, you might as well just enumerate all the vertices.