Algorithms in a Nutshell

(^298) | Chapter 9: Computational Geometry
References
Akl, Selim G. and Godfried Toussaint, “A Fast Convex Hull Algorithm,”Informa-
tion Processing Letters, 7(5), 1978.
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Cliffort Stein,
Introduction to Algorithms, Second Edition. McGraw Hill, 2001.
Graham, R. L., “An Efficient Algorithm for Determining the Convex Hull of a
Finite Planar Set,”Information Processing Letters 1: 132–133, 1972.
Melkman, A., “On-line construction of the convex hull of a simple polygon,”
Information Processing Letters 25: 11–12, 1987.
Overmars, Mark and Jan van Leeuwen, “Maintenance of Configurations in the
Plane,”Journal of Computer and System Sciences, 23(2): 166–204, 1981.
Palazzi, Larry and Jack Snoeyink, “Counting and Reporting Red/Blue Segment
Intersections,”CVGIP: Graphical Models and Image Processing, 56(4): 304–310,
1994.
Preparata, Franco and Michael Shamos,Computational Geometry: An Introduc-
tion. Springer-Verlag, 1985.
Table 9-8. Brute force Range Query execution times in milliseconds for situation 3
n d=2 BF d=3 BF d=4 BF d=5 BF
4,096 9.625 10.5 10.125 10.25
8,192 20.75 20.875 21.875 23.875
16,384 41.375 46.125 46.375 51
32,768 90.75 97.25 97.875 105
65,536 201.875 187.125 198.375 217.25
131,072 400.5 386.375 400.375 411.375
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