Algorithms in a Nutshell

Convex Hull Scan | 263

Computational

Geometry

initial points, and since these points are discarded before the sort operation, the

costly sorting step in the algorithm is reduced.

Forces

CONVEXHULLSCANrequires only primitive operations (such as multiply and

divide), making it easier to implement than GRAHAMSCAN(Graham, 1972),

which requires using trigonometric identities. If CONVEXHULL SCANuses

QUICKSORTto initially sort the points, its performance suffers because of the

well-documented problems that QUICKSORThas with nearly sorted data (see

“Quicksort” in Chapter 4). CONVEXHULLSCANcan support a large number of

points since it is not recursive. The implementation in Example 9-2 uses arrays; if

it used linked lists, then it would use INSERTIONSORT, which would worsen the

performance to O(n^2 ). Using balanced binary trees to store the input points

instead of arrays would eliminate the sorting step, yet add extra complication to

the code requesting the convex hull. The fastest implementation occurs if the

input set is uniformly distributed and so it can be sorted in O(n) using BUCKET

SORT, since the resulting performance would also be O(n). The supporting code

repository contains each of the described implementations that we benchmark for

performance later in the “Analysis” section.

Solution

Example 9-2 shows how CONVEXHULLSCANfirst computes the partial upper

hull before reversing direction and computing the partial lower hull. The final

convex hull is the combination of the two partial hulls. Figure 9-11 summarizes

thePartialHull class.

Figure 9-10. The Akl-Toussaint heuristic at work

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