Algorithms in a Nutshell

Convex Hull Scan | 265

Computational

Geometry

Consequences

Because the first step of this algorithm must sort the points, we rely on HEAP-

SORTto achieve the best average performance without suffering from the worst-

case behavior of QUICKSORTas described in Chapter 4. However, in the average

case, QUICKSORTwill outperform HEAPSORT, so you should consider the likeli-

hood that the worst case for QUICKSORT will occur.

Analysis

We ran a set of 100 trials on randomly generated two-dimensional points from

the unit square; the best and worst trials were discarded, and Table 9-3 shows the

average performance results of the remaining 98 trials. The table also shows the

breakdown of average times to perform the heuristic plus some information about

the solution.

Given a uniform distribution ofnrandom points within the [0,1] unit square,

Table 9-3 describes statistics that reveal some of the underlying reasons for why

CONVEXHULLSCAN is so efficient.

As the size of the input set increases, nearly half of its points can be removed by

the Akl-Toussaint heuristic. More surprising, perhaps, is the low number of

points on the convex hull. The second column in Table 9-3 validates the claim by

Preparata and Shamos (1985) that the number of points should be O(logn),

which may be surprising given the large number of points. One insight behind this

low number is that in a large random set, each individual point has a small proba-

bility of being on the convex hull.

The first step in CONVEXHULLSCANexplains the cost of O(nlogn) when the

points are sorted using one of the standard comparison-based sorting techniques

described in Chapter 4. As previously mentioned, if the points are already sorted,

then this step can be skipped and the resulting steps require just O(n) processing.

Table 9-3. Example showing running times (in milliseconds) and applied Akl-Toussaint

heuristic

n

Average

number of

points on hull

Average time

to compute

Average

number of

points

removed by

heuristic

Average time

to compute

heuristic

Average time

to compute

with heuristic

4,096 21.65 8.95 2,023 1.59 4.46

8,192 24.1 18.98 4,145 2.39 8.59

16,384 25.82 41.44 8,216 6.88 21.71

32,768 27.64 93.46 15,687 14.47 48.92

65,536 28.9 218.24 33,112 33.31 109.74

131,072 32.02 513.03 65,289 76.36 254.92

262,144 33.08 1168.77 129,724 162.94 558.47

524,288 35.09 2617.53 265,982 331.78 1159.72

1,048,576 36.25 5802.36 512,244 694 2524.30

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