Point Location in Constant Time

Sairam Chaganti, Yijie Han

We preprocess the input subdivision with $n$ points on the plane in $O(n\sqrt{\log n})$ time to facilitate point location in constant time. Previously the preprocessing time is $O(…