5
$\begingroup$

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.

$\endgroup$

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @Kurt: Ah, good point! $\endgroup$ Sep 7, 2011 at 19:15
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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...

$\endgroup$
2
  • 2
    $\begingroup$ Fukuda actually has the algorithm ("Motzkin double description") implemented (google cddlib or rcdd for a convenient R implementation). It is blazingly fast in practice. $\endgroup$
    – Igor Rivin
    Sep 7, 2011 at 21:30
  • $\begingroup$ Thanks @Joseph, I was already suspecting that a possible answer to this question would involve counting or enumerating vertices, so for those who are interested, I asked a question along this line:[cstheory.stackexchange.com/questions/8111/… in the TCS StackExchange site. I would still be curious to know if there is a way to do this without enumerating all vertices first. $\endgroup$
    – user12103
    Sep 8, 2011 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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