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.
-
The V(pi) is not necessarily convex, but it always star-shaped w.r.t.
the generator pi.
-
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.
-
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.
