Planar Point Location

References

Arge, L, J Vahrenhold. (2002) I/O Efficient Dynamic Planar Point
Location. SIAM Journal on Computing.

Arya, S, T Malamatos, DM Mount  (2000) Nearly Optimal Excpected-Case
Planar Point Location. In: 41st Annual Symposium on Foundations
of Computer Science.  Redondo Beach, CA, USA. Nov. 12-14.

de Berg, M, M van Kreveld, M Overmars, O Schwarzkopf (2000)
Computational Geometry: Algorithms and Applications, 2nd
Edition. Springer: Berlin Heidelberg. 367p

Dobkin, D, RJ Lipton (1976)  Multidimensional search problems. 
SIAM Journal on Computing 5(2): 181-186.

Edelsbrunner, H, LJ Guibas, J Stolfi (1986)  Optimal Point Location 
in a Monotone Subdivision. SIAM Joural on Computing. 15(2):317-340.

Kirkpatrick, D (1983) Optimal Search in Planar Subdivisions.  SIAM 
Joural on Computing. 12(1):28-35.

Iacono, J., S Langerman. (2003)  Proximate Planar Point Location.  
In: SoCG’03 June 8-10, San  Diego, California, USA. 

Mulmuley, K (1990)  A Fast Planar Partition Algorithm, I.  Journal of 
Symbolic Computation. 10:253-280.

Preparata, FP, MI Shamos (1985) Computational Geometry: An Introduction. 
Springer-Verlag: New York. 390p.

Sarnak, N, RE Tarjan (1986) Planar point location using persistent search 
trees. Communications of the ACM. 29:669-679.

Seidel, R (1991) A simple and fast incremental randomized algorithm for
computing trapezoidal decompositions and for triangulating polygons. 
Computational Geometry: Theory and Applications. 1:51-64.

Acknowledgements

I would like to thank Derek Bradley for providing me with Java source code from his project page for Kirkpatrick's algorithm (see below).

Other Resources

Derek Bradley's Project describing Kirkpatrick's Algorithm

Jukka Kaartinen's Project describing Trapezoid Map Generation

Another good description of planar point location using trapezoid maps is this project by Sergi Elizalde & David Pritchard