We can also refer to Voronoi diagram defined with the supermum metric, such a Voronoi diagram is called Supermum metric Voronoi diagram. The Supermum-metric Voronoi diagram is quite similar to the manhattan Voronoi diagram.
Generally, if we rotate the x₁-x₂ plane in manhattan-metric with generators counterclockwise by π/4, we obtain diagram in the supermum metric.
Specifically, if we rotate the bisector defined with the Manhattan metric counterclockwise by π/4, we obtain the bisector defined with the supermum metric.

Outline of an Algorithm using above property

1. First, the supermum-metric Voronoi Diagram of P is obtained by rotating P counterclockwise by π/4.
2. Next, construct the Manhattan Voronoi Diagram for the rotated set of points.
3. Finally, rotate the resultant diagram by π/4.