(^266) | Chapter 9: Computational Geometry
The loop that computes the upper partial hull (lines 4–7 in Figure 9-7) processes
n–2 points; the innerwhileloop (lines 6–7) cannot execute more thann–2 times,
and the same logic applies to the loop that computes the lower partial hull (lines
9–12). The total time for the remaining steps of CONVEXHULLSCANis thus
O(n).
Problems with floating-point arithmetic appear when CONVEXHULLSCAN
computes the cross product calculation. Instead of strictly comparing whether the
cross productcp<0,PartialHull determines whethercp<δ, whereδ is 10–9.
Variations
The sorting step of CONVEXHULLSCANcan be eliminated if the points are
already known to be in sorted order; in this case, CONVEXHULLSCANcan
perform in O(n). Alternatively, if the input points are drawn from a uniform distri-
bution, then one can use BUCKETSORT(see “Bucket Sort” in Chapter 4) to also
achieve O(n) performance. Another convex hull variation known as QUICKHULL
(Preparata and Shamos, 1985) uses the “divide and conquer” technique inspired
by QUICKSORT to compute the convex hull.
There is one final variation to consider. CONVEXHULLSCANdoesn’t actually
need a sorted array when it constructs the partial upper hull; it just needs to
iterate over all points inPin order, from smallestxcoordinate to highestxcoordi-
nate. This behavior is exactly what occurs if one constructs a binary heap from the
points inPand repeatedly removes the smallest element from the heap. If the
removed points are stored in a linked list, then the points can be simply “read off”
the linked list to process the points in reverse order from right to left. The code for
this variation (identified as Heap in Figure 9-12) is available in the code reposi-
tory accompanying this book.
The performance results shown in Figure 9-12 were generated from three data set
distribution types:
Circle data
npoints distributed evenly over the unit circle. Note that all of these points
will belong to the convex hull, so this is an extreme case.
Uniform data
npoints distributed evenly over the unit square. Asnincreases, the majority
of these points will not be part of the convex hull, so this represents another
extreme case.
Slice data
npoints distributed unevenly;n–2 points are clustered in thin slices just to
the left of .502. The data set also contains the point (0,0) and (1,0). This set is
constructed to defeat BUCKETSORT.
We ran a series of trials using data sets of sizen= 512 to 131,072 points,*the two
data set distributions, and the different implementations described in Example 9-2
- We limited the slice data set size to 2,048 because BUCKETSORTrapidly degenerated to O(n^2 )
performance.
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use