2 deleted 1 characters in body

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

1

# Finding a hyperplane that splits a convex polytope evenly

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