Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  Robert Israel Aug 23 '12 at 6:43
    
Thenk you. Yes, that's what I ment. Also, my first question was for any point on the polytope. So I know only vertices. –  user202312 Aug 23 '12 at 6:56

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
    
Yhank you. But if the polytope is generated by the intersection of two simpleses, like in 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.... –  user202312 Aug 24 '12 at 19:55
    
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. –  Robert Israel Aug 24 '12 at 20:38
    
Thank you. I've asked this interesting problem as a separate question here:math.stackexchange.com/q/187177/37760 –  user202312 Aug 26 '12 at 17:26

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.