Title: Optimal Expected-Case Planar Point Location
Speaker: Wong Ka Chun
HKUST


Date: Friday December 3, 2004
Time 11-12
Venue: Room 3501, HKUST


Abstract
We study the planar point location problem, a fundamental problem in
computational geometry, from the perspective of expected query time.
Given a 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
the goals of H + o(H) expected query time and O(n) space. In my talk,
I will present such a solution.

(Joint work with Sunil Arya, Theocharis Malamatos, and David Mount)