On the exact worst case query complexity of planar feint location

What is the smallest constant c so that the planar point location queries c an be answered in c log(2) n + o(log n) steps (i.e., point-line comparisons ) in the worst case? M. T. Goodrich, M. Orletsky, and K. Ramaiyer (1997, in "Proc 8th ACMSIAM Symp on Discrete Algorithms (SODA)," pp. 757-766) showed that c = 2 is possible using linear space and conjectured this to be optim al. We disprove this conjecture and show that c = 1 can be achieved. Moreov er 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 root 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 root log(2) n + O(log(1/4) n). (C) 2000 Academic Press.