References

• M. de Berg et al. Computational Geometry, Algorithms and Applications. 2nd Ed. Ch 6: pp 121-146. Springer-Verlag 2000.
  
  
• H. Edelsbrunner, L.J. Guibas, J Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15:317-340, 1986.
  
  
• D. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28-35, February 1983.
  
  
• K. Mulmuley. A fast planar partition algorithm, I. Proc. 29th Ann. IEEE Symp. Found. Comp. Sci., pp 580-589, 1988.
  
  
• N. Sarnak & R.E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29:669-679, 1986.
  
  
• M. Smid. Point location in planar subdivisions. September 2003.
  
  

Links

Here are some links to other websites that contain information about the point location problem.

• http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2002/PaulSandulescu/
• http://www.cs.sunysb.edu/~algorith/files/point-location.shtml
• http://theory.lcs.mit.edu/~indyk/6.838/handouts/lec6.pdf
• http://cs.nyu.edu/visual/home/demos/pointLocation/demo.html (a different point location applet - takes a long time to download)
• http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE190.HTM

Here are a few other websites of relevance.

• Carleton University School of Computer Science
• Professor Michiel Smid's Website
• Derek Bradley's Website