Q:

Compute the point of contraction of a bounded region in $\mathbb{R}^n$

Say we have a list of linear inequalities that define a bounded region in $\mathbb{R}^n$.  These inequalities are: $a_1 \cdot x \ge c_1, \dots, a_k \cdot x \ge c_k$.  Assume general position (i.e. it is never true that $a_h = \lambda a_j$).
Rewrite the list as $a_1 \cdot x \ge c_1 + \epsilon, \dots, a_k \cdot x \ge c_k + \epsilon$.  Let $\epsilon_f$ be the largest $\epsilon$ such that the region remains nonempty.
One:

My geometric intuition says that $a_1 \cdot x \ge c_1 + \epsilon_f, \dots, a_k \cdot c_k + \epsilon_f$ is always solved by exactly one point in $\mathbb{R}^n$.  Is this correct?

Two:

If so, what is the asymptotically fastest algorithm for computing this point?

Thanks!

A:

Generic position requires more than non-collinearity of any two vectors $a_j$. To see why, imagine a  tall triangular prism with non-parallel top and bottom faces. Here none of the faces are parallel to each other, but the  set described with $\epsilon_f$ is a line. The problem is that the three vertical sides of the prism have coplanar normal vectors. 
Thus, you should also require that the vectors $a_j$ are in the generic position, in the following sense: for all $m\le \min(k,n)$, any $m$ of these vectors span an $m$-dimensional subspace.  
Then the answer is yes: the inequalities with $\epsilon_f$ determine a unique point. Indeed, the set they define must have empty interior, otherwise $\epsilon_f$ would not be the maximal possible. Suppose that they alternative is that they define a $d$-dimensional convex set $K$ for some $1\le d\le n-1$. Let $N$ be the orthogonal complement of the affine span of $K$. The dimension of $N$ is $n-d$. The vectors that are active constraints for $K$ must lie in $N$. To define a $d$-dimensional set by linear inequalities, we need  at least $n-d+1$ inequalities. Thus, these $n-d+1$ vectors lie in an $n-d$-dimensional subspace, contradicting the assumption of generic position. 
Concerning  algorithms,  I refer to StackOverlow discussion. Note that the term "Chebyshev center" is sometimes used for the point you described (which is the center of the largest  ball contained in the polytope), while at other times it is used for the center of the smallest containing ball.

