Voronoi diagram boundaries with Manhattan distance

I’m trying to draw a voronoi diagram using the Manhattan distance by hand, and I’m becoming very confused because it appears as though the boundary is an area rather than a line. This seems completely wrong to me and conflicts with the manhattan distance voronoi diagrams I’ve seen (boundaries are lines).

Can someone explain what I’m seeing?

Illustration

Answer

I’d say the picture you provided is correct, but it describes a special situation. To be more precise, the special thing about the configuration you gave is that the two points lie on a line with slope 1, so there is a critical point exactly to the left of one point and exactly below the other. No matter how you reach that critical point from the quadrant below and to the left, you can always continue to both points with the same additional distance. So yes, all the points in the areas with the question marks are the same distance from the both your points, and therefore by definition part of the boundary.

But as I said, this is a special situation. If you perturb the configuration even a very slight bit, then you’ll end up with a slight difference between x distance and y distance. See e.g. this blog by Arthur Charpentier for an illustration (right part for Manhattan distance):

Illustration

Here, the y difference is (quite a bit) larger than the x difference. As a result, points below the horizontal line on the left belong to the lower point, because they can avoid a bit of vertical distance to that point.

So it very much depends on whether you want to deal with special point configurations (like your situation), or are only interested in general position (like the one depicted above).

Attribution
Source : Link , Question Author : user2345397 , Answer Author : MvG

Leave a Comment