Voronoi cells for rectangles

Question

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?

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.