Manhattan-Metric Voronoi Diagram


In Manhattan Voronoi Diagram, the bisector defined with Manhattan metric and hence the set VM  = {V(p1), . . ., V(pn)} defined by the equation 1 with equation 2 (p=1) gives a generalized Voronoi diagram.

We call the set VM the Manhattan-Metric Voronoi Diagram generated by Manhattan Voronoi Diagram in brief, and the set V(pi) the Manhattan metric Voronoi polygon associated with pi.

(Fig 3.7.3 p 187)



The set V(pi) defined by Minkowski metric with the Manhattan metric is not empty, and forms a Manhattan Voronoi polygon.

  1. The V(pi) is not necessarily convex, but it always star-shaped w.r.t.  the generator pi.
  2. Every edge of V(pi) consists of at most three straight lines that are parallel to the x1-axis, x2-axis, or diagonal lines within angle π/4 3π/4.
  3. The V(pi) is infinite if pi is on the boundary of the convex hull of p, but not conversely.