## 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)

### Properties

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.

### Reference

• G.M. Carter, J.M. Chaiken and E. Ignall , "Response area for two emergency units, operators Research," 20(1972), 571-594.
• F.K. Hwang , "An O (nlogn) algorithm for rectilinear minimal spanning trees", Journal of the ACM, 26(1979), 177-182.
• D.T. Lee, "Two dimensional Voronoi Diagram in the Lp-metric, Journal of the ACM", (1980)27, 604-618.
• D. T Lee and C. K. Wong, "Voronoi Diagram in L1 (L) metrics with 2-dimensional storage applications",  SIAM Journal of Computing, 9(1980), 200-211.