Algorithms in a Nutshell

LineSweep | 279

Computational

Geometry

Thus theline state will never store more thannline segments. The operations that

probe the line state can be performed in O(logn) time, and since there are never

more than O(n+k) operations over the state, our cost is O((n+k) log (n+k)).

Becausekis no larger than C(n,2) orn*(n–1)/2, the inner equation can be simpli-

fied as follows:

O((n+k) log (n+k)) = O((n+k) log (n*(n+1)/2))

Now, using the properties of logarithms, the following is true:

log (n*(n+1)/2) = logn + log (n+1) – log 2≤ logn + log (2n) – 1≤ 2 logn

which results in the following:

O((n+k) log (n*(n+1)/2)) = O(2*(n+k) logn)

therefore the overall performance is demonstrably still O((n+k) logn).

Because the performance of LINESWEEPis dependent upon complex properties of

the input (i.e., the total number of intersections, the average number of line

segments maintained by the sweep line at any given moment), we can only bench-

mark its performance given a specific problem and input data. We’ll discuss two

such problems now.

An interesting problem from mathematics is how to compute an approximate

value ofπusing just a set of toothpicks and a piece of paper (known as Buffon’s

needle problem). If the toothpicks all arelenunits long, then draw a set of vertical

lines on the paper,dunits apart from one another whered≥len. Randomly tossn

toothpicks on the paper and letkbe the number of intersections with the vertical

lines. It turns out that the probability that a toothpick intersects a line (which can

be computed ask/n) is equal to (2*len)/(π*d).*

When the number of intersections is much less thann^2 , the BRUTEFORCEINTER-

SECTIONalgorithm will waste time checking lines that don’t intersect (as we see

in Table 9-4). When there are many intersections, the determining factor will be

the average number of line segments maintained byLineStateduring the dura-

tion of LINESWEEP. When it is low (as might be expected with random line

segments in the plane), LINESWEEP will be the winner.

*http://mathworld.wolfram.com/BuffonsNeedleProblem.html

Table 9-4. Timing comparison (in milliseconds) between algorithms on Buffon’s needle

problem

n LineSweep Brute Force

Average number

of intersections Estimate forπ

16 479.5918 0 1.02 3.147541

32 153.0612 0 2.14 3.047619

64 469.3878 0 3.99 3.324675

128 316.3265 795.9184 8.53 3.213389

256 1255.102 3346.939 17.83 3.237092

512 4448.98 10357.14 40.48 3.191688

1,024 8448.98 44408.16 97.15 3.223505

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