0
$\begingroup$

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?

1 Answers 1

1

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.