Algorithms in a Nutshell

(^280) | Chapter 9: Computational Geometry
In the worst case—that is, when there are O(n^2 ) intersections among the line
segments—LINESWEEPwill seriously underperform because of the overhead in
maintaining the line state in the face of so many intersections. Table 9-5 shows
how the BRUTEFORCEalgorithm handily outperforms LINESWEEP, wherenis
the number of line segments whose intersection creates the maximum ofn*(n–1)/2
intersection points.
Variations
One interesting variation requires only that the algorithm report one of the inter-
section points, rather than all points; it would be useful to detect whether two
polygons intersect. This algorithm requires only O(nlogn) time, and may more
rapidly locate the first intersection in the average case. Another variation
considers an input set of red and blue lines where the only desired intersections
are those between different colored line segments (Palazzi and Snoeyink, 1994).
Nearest Neighbor Queries
Given a set of pointsPin a two-dimensional Cartesian plane, answer nearest
neighbor queries of the form, “What point inPis closest to pointx?” Note thatx
does not have to be a preexisting point inP. These queries also extend to input
sets whose points are found inn-dimensional space. The naïve implementation is
to inspect all points inP, resulting in a linear O(n) algorithm. SincePis known in
advance, perhaps there is some way to structure its information to speed up
queries by discarding from consideration large groups of points inP.
2,048 22122.45 172234.7 263.07 3.086274
4,096 61632.65 685438.8 789.46 3.152588
Table 9-5. Worst-case comparison of LineSweep versus BruteForce (in ms)
n LineSweep (avg) BruteForce (avg)
200
4 0.1531 0
8 0.6429 0
16 0.6327 0
32 6.4082 0.6327
64 36.7959 0.6429
128 218.2551 3.2245
256 1566.4898 34.5918
512 9791.4592 209.0102
Table 9-4. Timing comparison (in milliseconds) between algorithms on Buffon’s needle
problem (continued)
n LineSweep Brute Force
Average number
of intersections Estimate forπ
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