Planar point location is one of the most important search problems in computational geometry. Given a set of non-overlapping polygons in the plane, the goal is to build a data structure for finding efficiently the polygon in which a query point lies. In terms of the worst-case query time, several methods are known for solving the problem optimally. We focus instead on optimizing the expected-case query time of planar point location. The analogous problem in one dimension is that of building optimal binary search trees....[ Read more ]

Planar point location is one of the most important search problems in computational geometry. Given a set of non-overlapping polygons in the plane, the goal is to build a data structure for finding efficiently the polygon in which a query point lies. In terms of the worst-case query time, several methods are known for solving the problem optimally. We focus instead on optimizing the expected-case query time of planar point location. The analogous problem in one dimension is that of building optimal binary search trees.

We assume that we are given a set of non-overlapping polygons and for each polygon the probability that a query point lies in it. These probabilities define a probability distribution whose entropy we denote by H. By fundamental results of information theory, the expected query time must be at least H. We develop methods for answering planar point location queries in expected query time nearly matching the entropy lower bound, using close to linear space. In particular, the expected number of comparisons for locating the query point by our methods is at most H plus lower order terms. These results hold for polygons having a constant number of sides and convex polygons with uniform query distribution in their interiors. In special cases, such as planar subdivisions consisting of axis-parallel rectangles, we reduce the space to linear.

We also present a practical method that achieves O(H) expected query time, which is optimal to within a small multiplicative factor.