The following is a problem of "Digital image processing" book.

Consider two points $p$ and $q$. State the condition(s) under which the $D_4$ distance between $p$ and $q$ is equal to the shortest 4-path between these points.

And the following is the solution in "solution manual"

This occurs whenever we can get from $p$ to $q$ by following a path whose elements (1) are from V, and (2) are arranged in such a way that we can traverse the path from $p$ to $q$ by making turns in at most two directions (e.g., right and up). [The black path in the following figure.]

But I don't understand why other "right angle" paths, such as the red one in the following figure, are not the solution. Why there must be at most only two directions?

P.S. For pixels $p$ and $q$ with coordinate $(x, y)$ and $(s, t)$, respectively, the $D_4$ distance is as $|x-s| + |y - t|$.

enter image description here


  • $\begingroup$ Both red and back paths meet the criteria of the solution. Both only go "up" and "right". I think the use of the word "turns" is a bit confusing here. $\endgroup$
    – Hilmar
    Jun 29 at 6:40
  • $\begingroup$ @Hilmar Thanks a lot, I think I got it. The "two directions" is matter, not the number of turns. $\endgroup$
    – user153245
    Jun 29 at 9:08

The $ D_4 $ distance in your definition is basically what's called the $ L_1 $ norm based distance or Manhattan Distance.

It is also called Taxicab Distance or Taxicab Geometry.
From its name you can understand that as long as you walk on straight lines and turning towards the target (If its up and right so you turn only up and right, if it is left and down you turn only left and down) all paths have the same distance using this norm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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