Manhattan distance of a point and a line

Xavier Décoret

The distance between a point $P$ and a line $L$ is defined as the smallest distance between any point $M\in L$ on the line and $P$ :

$$d(P,L) \equiv \min_{M\in L} d(M,P)$$

The manhattan distance between two points is defined as:

$$d(M,P) \equiv \vert M_x-P_x\vert+\vert M_y-P_y\vert$$

The question is then ``what is the formula that gives the manhattan distance between a point and a line?''.

Proposition 1   The manhattan distance between a point of coordinates $(x_0,y_0)$ and a line of equation $a x+b y+c=0$ is given by :

$$\frac{\vert a x_0+b y_0+c\vert}{\max(\vert a\vert,\vert b\vert)}$$

Since $a$ and $b$ can not be both 0, the formula is legal.

Proof. The proof is in two steps. First we prove that the minimum distance is obtained for the vertical or horizontal projection of the point onto the line. We have (see fig. 1):

Figure 1:

$$d(P,M_h) = w+w'$$

$$d(P,M_v) = h+h'$$

$$d(P,M) = w+h$$

$$= w+\tan\alpha\ w'$$

$$= \frac{1}{\tan\alpha}h'+h$$

Thus, if $\tan\alpha<1$ , we have $d(P,M)<d(P,M_h)$ and otherwise $d(P,M)\leq d(P,M_v)$ .

Next, we need to compute the two distances. For the horizontal one, we must solve:

$$ax+by+c = 0$$

$$y = y_0$$

which gives $x = \frac{1}{a}(-b y_0-c)$ . The distance is then $d(M_h,P)=\vert x-x_0\vert=\frac{\vert a x_0+b y_0+c\vert}{\vert a\vert}$ . Doing the same for the vertical one yields the $d(M_v,P)=\frac{\vert a x_0+b y_0+c\vert}{\vert b\vert}$ . We conclude by noting that $\min(\frac{1}{\vert a\vert},\frac{1}{\vert b\vert})=\frac{1}{\max(\vert a\vert,\vert b\vert)}$ . $\qedsymbol$