Supremum-Metric Voronoi Diagram

 

    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 x1-x2 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.
Figure 3.7.5 <p. 189>



Reload