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?
Voronoi cells for rectangles
reference request;computational geometry
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.