How to find on each face of a polyhedron one point?

Question

We have a polyhedron in $\mathbb R^n$ generated by the intersection of a collection of finete hyperplanes or the convex hull of the set of vertices.

My question is: Is there any algorithm for finding on each face of that polyhedron one point (that is not a vertex).

Answer 1

For case 2, apply a convex hull algorithm to determine which verts are ON the convex hull. Throw out the others. Now for each facet of the convex hull (which I'm expecting your chull algorithm will give to you; the Preparata-et-al one does, I believe), form the convex hull of its vertices (there might be three verts forming a triangle, for instance, and one of them that's a midpoint of an edge, or is interior to the triangle). Eliminate all those that are convex combinations of others. Then consider the average of the vertices that remain: it'll be an interior point of the facet.

Answer 2

Unfortunately, I am a little late, but I think it is worth considering the following answer.

For the case of $\mathcal{H}$-polyhdra, i.e. the polyhedron is given as intersection of finitely many half-spaces, I propose the folloiwng procedure.

Let $P= \{\mathbf{x} \mid A\mathbf{x} \leq \mathbf{a}, B\mathbf{x} = \mathbf{b}\}$ be a $\mathcal{H}$-polyhedron, where $A$ and $B$ are matrices, and $\mathbf{a}$ and $\mathbf{b}$ are vectors. Further let $\mathbf{1}$ be a vector whose coefficients are equal to 1.

Let $\lambda_0$ be the optimal value of the linear program:

$\quad$maximize $\lambda$ such that $A\mathbf{x} + \mathbf{1}\lambda \leq \mathbf{a}, B\mathbf{x} = \mathbf{b}, \lambda \leq 1$.

The linear program is always feasible and there are three cases:

1. $\lambda_0 < 0$: Then $P$ is empty.
2. $\lambda_0 = 0$: Then the vector $x_0$ of the optimal solution $(x_0, \lambda_0)$ is a relatively interior point of $P$.
3. $\lambda_0 > 0$: Then $P$ contains implicit equalities, i.e. some of the inequalities in $A\mathbf{x} \leq \mathbf{a}$ can be changed to equalities without changing $P$. The respective rows can be read off the dual solution of the linear program.

Now, proceed as follows:

Step 1: Solve the linear program. In case 1) there will be no solution. In case 3) make the implicit equalities explicit by moving them to the system $B\mathbf{x} \leq \mathbf{b}$. Solve the linear program again until you found a relative interior point of $P$.

Step 2: Now, we have a representation of $P$ without implicit equalities. Hence, any row in the subsystem $A\mathbf{x} \leq \mathbf{a}$ is either redundant or corresponds to a facet of $P$. For any row of $A\mathbf{x} \leq \mathbf{a}$ we proceed as follows: Remove the row from $A\mathbf{x} \leq \mathbf{a}$ and move it to the system $B\mathbf{x} = \mathbf{b}$ instead. Now proceed with this system as in step 1. Either the system is not solvable, and the chosen row is redundant, or you will find a relatively interior point of the facet, which is exactly what you asked for.

Hence, the proposed algorithm will find a minimal representation of $P$ where all implicit equalities are made explicit. It also provides a relative interior point on each facet of $P$.

For more details on the linear program see Fukuda's Lecture Notes http://stat.ethz.ch/ifor/teaching/lectures/poly_comp_ss11/lecture_notes on page 55. There you will also find further information how to read off the implicit equalties of the dual solution.