@article {15652,
title = {Optimal expected-case planar point location},
journal = {SIAM Journal on Computing},
volume = {37},
year = {2007},
month = {2007///},
pages = {584 - 584},
abstract = {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.
},
author = {Arya,S. and Malamatos,T. and Mount, Dave and Wong,K.C.}
}