Planar point location is a central and important problem in computational geometry. Given a polygonal partition of the plane one is to build a data structure so that queries of the form ``which polygon of the partition contains a given query point'' can be answered quickly. It has been known for a long time that this problem admits a solution with O(log n) worst case query time using O(n) space, where n is the total number of polygon edges in the partition.

In SODA 97 Goodrich, Orletsky, and Ramaiyer asked for the smallest constant c, so that planar point location queries can be answered in c log n + o(log n) steps (i.e. point-line comparisons) in the worst case. They showed that c=2 is possible (using linear space) and conjectured this to be optimal.

I will disprove this conjecture and show that even c=1 can be achieved. Moreoever by giving a nontrivial lower bound I will determine this worst case query complexity almost exactly, namely up to an additive factor of loglog n + O(1).