%0 Journal Article %J SIAM Journal on Computing %D 2007 %T Optimal expected-case planar point location %A Arya,S. %A Malamatos,T. %A Mount, Dave %A Wong,K.C. %X 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. %B SIAM Journal on Computing %V 37 %P 584 - 584 %8 2007/// %G eng %N 2