Algorithms in a Nutshell

(^260) | Chapter 9: Computational Geometry
Convex Hull Scan
To develop an efficient algorithm for computing the convex hull (whose fact sheet
appears in Figure 9-7) for a set of pointsP, we could choose an iterative approach,
as shown in Figure 9-8. To determine the next point in the hull, compute the
smallest angular difference formed by all non-hull points with an infinite ray
determined by the last two discovered hull points. When the partial convex hull
containshpoints, the angles must be computed forn–hpoints to determine the
next point; this approach is unable to prune away wasted computations that will
clearly not be needed.
Andrew’s CONVEXHULLSCANdivides the problem into two parts—constructing
the partial upper hull and the partial lower hull. First, all points are sorted by their
xcoordinate (breaking ties by considering they). Note that the points in
Figure 9-8 are already numbered from left to right along thexaxis. The partial
upper hull starts with the leftmost two points in P. CONVEXHULLSCANextends
the partial upper hull by finding the pointpin P whosexcoordinate comes next
in sorted order after the partial upper hull’s last point Li.
If the three points Li–1,Liand the candidate pointpform a right turn, then CONVEX
HULLSCANextends the partial hull to includep. This decision is equivalent to
computing the determinant of the three-by-three matrix shown in Figure 9-9, which
represents the cross productcp=(Li.x–Li–1.x)(p.y–Li–1.y)–(Li.y–Li–1.y)(p.x–Li–1.x). If
cpis negative, then the three points determine a right turn and CONVEXHULL
SCANcontinues on. Ifcp=0 (the three points are collinear) or ifcp>0 (the three
points determine a left turn), then the middle point Limust be removed from the
partial hull to retain its convex property. CONVEXHULLSCANcomputes the
convex upper hull by processing all points up to the rightmost point. The lower
hull is similarly computed (this time by choosing points in decreasingxcoordi-
nate value), and the two partial hulls are joined together.
Figure 9-7 shows CONVEXHULLSCANin action as it computes the partial upper
hall. Note that the overall approach makes numerous mistakes as it visits every
point inPfrom left to right, yet all of these are corrected by dropping—some-
times repeatedly—the middle of the last three points.
Nearest Neighbor public class KDTree {
/* Return closest point to target. /
public IMultiPoint nearest (IMultiPoint target);
}
Obvious solution: O(n)
Average-case kd-tree NEARESTNEIGHBOR: O(logn)
Range Queries public class KDTree {
/* Return points within region. /
public ArrayList search (
IHypercube space);
}
Obvious solution: O(n)
Average-case kd-tree RANGEQUERY: withr=number of reported points
Table 9-2. API definition of problems discussed in this chapter (continued)
Problem API description
O()nr+
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