Abstract
We study the planar point location problem, a fundamental problem in computational geometry, from the perspective of expected query time. Given a planar polygonal subdivision S of size n and the probability of the query point lying in each cell of S, the goal is to construct a data structure that minimizes the expected query time. It is well-known that the entropy H of the resulting discrete probability distribution is a lower bound on the expected query time. In one dimension, data structures of linear size whose expected query time matches the entropy lower bound were discovered more than 20 years ago. But in two dimensions, there is no known approach that simultaneously achieves H + o(H) expected query time and O(n) space. In this thesis, we present such a solution.