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
    If you know the vertices, and you know the point, just calculate all the distances and take the least one. I'm not sure what you mean by "from the farest polytope point to the closest vertex of the polytope". Do you mean you want to find a point of the polytope that maximizes the minimum distance to a vertex?2012-08-23
  • 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
    Yhank you. But if the polytope is generated by the intersection of two simpleses, like in http://math.stackexchange.com/a/181789/37760, is it possible to give the presise answer to my question above? It seems, the polytope is more or less symmetric at this case....2012-08-24
  • 0
    Suppose (as in the case you mention) there is a group $G$ of isometries of the polytope $P$ that is transitive on the vertices. Then I suspect the maximum is attained at the barycentre. I don't see a proof right now, though.2012-08-24
  • 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)$