0
$\begingroup$

How to find distance in between any polytope point to the closest vertex of the polytope (the verteces of the polytope are known)?

How to find a distance from the farest polytope point to the closest vertex of the polytope?

  • 0
    Thenk you. Yes, that's what I ment. Also, my first question was for any point on the polytope. So I know only vertices.2012-08-23

2 Answers 2

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

  • 0
    Thank you. I've asked this interesting problem as a separate question here:http://math.stackexchange.com/q/187177/377602012-08-26
0

Not assuming convexity, you will have to test each possibility. Given your point $p$ and the locations of each vertex $v_i \in V$, you want the vertex with minimum distance from $p$ (not unique). Let $dist(p,v_i)$ be a function that gives the distance from $p$ to $v_i$. The pseudo code for this is:

$v_{min} = v_1$
$d_{min} = dist(p,v_1)$
for $v_i \in V$
   if $dist(p,v_i) < d_{min}$
       $v_{min} = v_i$
       $d_{min} = dist(p,v_i)$