I am looking for a reference on the following variant of a Voronoi diagram:

  • Instead of seed points, there are seed rectangles which are axis-parallel and pairwise-disjoint.
  • Instead of Euclidean distance, we are interested in Manhattan distance.

The goal is to partition the plane into regions, such that the points in each region $i$ are closer (in Manhattan distance) to rectangle $i$ than to every other rectangle.

What would such cells look like? Are there algorithms for finding them?


1 Answer 1


Essentially, these Voronoi diagrams are problems about solving Voronoi problems for $L_1$ metric. Both $L_1$ and $L_\infty$ has efficient solutions for the case of points ($O(n \log n$) time complexity algorithms).

You might be interested in some of the Papadopoulou's papers.

For $L_\infty$ metric you can use the more general solution for polygon offset distance. (Gill Barequet, Matthew Dickerson, Michael T. Goodrich: Voronoi Diagrams for Convex Polygon-Offset Distance Functions. Discrete & Computational Geometry 25(2): 271-291 (2001)).

Since your rectangles are axis-paralle, the offset distance function will be same as $L_\infty$ metric. However, you will have trouble at the corners. I think, you will not have much difficulty in using their results. The algorithm presented by them is quite efficient too.

enter image description here

  • $\begingroup$ Thanks! The offset-distance looks just like what I needed. $\endgroup$ Feb 12, 2016 at 7:12

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.