ManhattanMetric Voronoi Diagram
In Manhattan Voronoi Diagram, the bisector defined with Manhattan metric
and hence the set V_{M } = {V(p_{1}), . . ., V(p_{n})}
defined by the equation 1 with equation 2 (p=1) gives a generalized Voronoi
diagram.
We call the set V_{M }the ManhattanMetric Voronoi Diagram generated by Manhattan
Voronoi Diagram in brief, and
the set V(p_{i}) the Manhattan metric Voronoi polygon associated
with p_{i}.
(Fig 3.7.3 p 187)
Properties
The set V(p_{i}) defined by Minkowski metric with the
Manhattan metric
is not empty, and forms a Manhattan Voronoi polygon.

The V(p_{i}) is not necessarily convex, but it always starshaped w.r.t.
the generator p_{i}.

Every edge of V(p_{i}) consists of at most three straight lines that are parallel
to the x_{1}axis, x_{2}axis, or diagonal lines within angle
π/4 3π/4.

The V(p_{i}) is infinite if p_{i} 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), 571594.

F.K. Hwang , "An O (nlogn) algorithm for rectilinear minimal spanning
trees", Journal of the ACM, 26(1979), 177182.

D.T. Lee, "Two dimensional Voronoi Diagram in the Lpmetric, Journal of the ACM",
(1980)27, 604618.

D. T Lee and C. K. Wong, "Voronoi Diagram in L_{1} (L_{∞}) metrics with 2dimensional
storage applications", SIAM Journal of Computing, 9(1980), 200211.