Algorithms in a Nutshell

Convex Hull Scan | 267

Computational

Geometry

and the code repository. As a baseline for comparison, we include performance

results for using HEAPSORTsimply to sort the points. We did not employ the Akl-

Toussaint heuristic. For each data set size, we ran 100 trials and discarded the

best- and worst-performing runs. The resulting average time (in milliseconds) of

the remaining 98 trials is depicted in Figure 9-12. One can clearly see the direct

correlation between the sort time and the times to compute the convex hull.

Figure 9-12. Performance of convex hull variations

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