MPhil Thesis Defence


"Optimal Expected-Case Planar Point Location"

By

Mr. Ka-Chun Wong


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 this thesis, we will present such a solution.


Date:				Monday, 17 January 2005

Time:				10:00a.m.-12:00noon

Venue:				Room 3007
				Lift 3

Committee Members:		Dr. Sunil Arya (Supervisor)
				Dr. Mordecai Golin (Chairperson)
				Dr. Chiew-Lan Tai



**** ALL are Welcome ****