
Computational Geometry and Its Application to GIS 139
FIGURE 7.10
QuickHull elimination procedure
T(n) = cn + T(n
1
) + T(n
2
)
where, n
1
and n
2
are the number of points remaining in the two buckets. It
should be a familiar fact from the QuickSort analysis that this running time
will be good as long as max(n
1
, n
2
) is not too close to n.
7.7 Voronoi Diagrams
A Voronoi diagram (like convex hull) is one of the most important structures
in computational geometry. A Voronoi diagram records information about the
spatial relationship among the objects such as which spatial object is close to
what other spatial object or objects.
Let P = p
1
, p
2
, .., p
n
be a collection ...