# What is the condition under which the length of shortest 4-path equal to $D_4$ distance?

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

Thanks

• 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. Jun 29 at 6:40
• @Hilmar Thanks a lot, I think I got it. The "two directions" is matter, not the number of turns. Jun 29 at 9:08

## 1 Answer

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.