On the exact worst case query complexity of planar point location
Udo Adamy, Raimund Seidel · 1998
What is the smallest constant c so that the planar point location queries can be answered in c log 2 n + o(log n) steps (i.e. point-line comparisons) in the worst case? In SODA 97 Goodrich, Orletsky, and Ramaiyer [6] showed that c = 2 is possible using linear space and conjectured this to be optimal. We disprove this conjecture and show that c = 1 can be achieved. Moreoever by giving upper and lower bounds we show that without space restrictions the worst case query complexity of planar point location differs from log 2 n + 2 p log 2 n at most by an additive factor of (1=2)log 2 log 2 n +O(1). For the case of linear space we show the query complexity to be bounded by log 2 n + 2 p log 2 n +O(log 1=4 n).