Distance between a polytope's point and a vertex

Question

Suppose that we have a polytope and that its vertices are known. How to find the distance

1. between a given polytope point and the closest vertex of the polytope?

2. from the farthest polytope point to the closest vertex of the polytope?

Answer 1

Let the polytope (say in ${\mathbb R}^n$) be defined by the system of inequalities $A x \le b$, where $A$ is an $m \times n$ matrix. Let the vertices be $p_j$, $j=1\ldots,v$. We can write the problem as

maximize $t$ subject to $A x \le b$ and $|x - p_j|^2 \ge t^2$ for $j = 1 \ldots v$.

It is not a convex problem. In principle you should be able to solve the Karush-Kuhn-Tucker equations, but I don't think it will be very simple, because there are lots of possibilities to consider. Your point could be in the interior of the polytope, in which case it is equidistant from $n$ vertices, or it could be on a $k$-dimensional face for any $k \in [1,2,\ldots,n-1]$ and equidistant from $k$ vertices (which may or may not be on that face).