Voronoi cells for rectangles
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 &amp; 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.