Optimal expected-case planar point location

Point location is the problem of preprocessing a planar polygonal subdivision S of size ninto a data structure in order to determine efficiently the cell of the subdivision that contains a
given query point. We consider this problem from the perspective of expected query time. We
are given the probabilities pz that the query point lies within each cell z ∈ S. The entropy H of
the resulting discrete probability distribution is the dominant term in the lower bound on the
expected-case query time. We show that it is possible to achieve query time H + O(
√
H + 1)
with space O(n), which is optimal up to lower order terms in the query time. We extend this
result to subdivisions with convex cells, assuming a uniform query distribution within each cell.
In order to achieve space efficiency, we introduce the concept of entropy-preserving cuttings.