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.

Let us have a set of $n$ points, $x_1, x_2, \ldots, x_n \in \mathbb{R}^d$, that form a convex polytope. And let us have a single point $x \in \mathbb{R}^d$ that is outside of the polytope. How can I compute the $l_1$ distance of the point to the polytope?

I wanted to do it similar to $l_2$ distance. That is, I check the distance for each line segment. Then I find the $l_2$ distance of a line segment to the point and get the minimum among the line segments. It can be done since I can find the smallest distance by using derivation. But, how to do it for $l_1$ distance?

share|improve this question
    
I wanted to do it similar to l2 distance. That is, I check the distance for each line segment. Then I find the l2 distance of a line segment to the point and get the minimum among the line segments. Don't do that, use quadratic programming for it. Look here under 'distances' for explanations of some special cases (distance point-triangle for example). –  Peter Sheldrick Jun 9 '12 at 17:06

1 Answer 1

up vote 1 down vote accepted

This is a linear program. First write the convex polytope as an intersection of linear inequalities and minimize $||x-y||_1$ for for $y$ in the polytope. So in 2D this is $|x_1-y_1|+|x_2-y_2|$. Now introduce two new variables $v_1,v_2$. Then minimize $v1+v2$ subject to $-v_1\leq x_1 - y_1 \leq +v1$, $-v_2\leq x_2 - y_2 \leq +v2$ and $y$ in convex polygon.

Determining the distance from a point to an (unbounded) line is also a linear program. Just minimize $||x-y||_1$ with $ay_1+by_2=c$ for some given $a,b,c$. You don't get such a nice formula for the closest point + distance as in the $l_2$ case. However this still has a derivative (that again isn't a single formula but a piecewise function). So if you program this it involves a few if statements... You go through the possibilities - in German there is the word Fallunterscheidung for that, but i'm not sure if there is a English equivalent.

EDIT: In fact the derivatives of functions involving absolute values may well be one formula, but don't expect them to be continuous everywhere.

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.