PhD Thesis Proposal Defence


"Expected-Case Planar Point Location"

By

Mr. Theocharis Malamatos


Abstract

Planar point location is a fundamental search problem in Computational
Geometry. The problem is to preprocess a polygonal subdivision of the
plane into a data structure so that the polygon containing a given query
point can be reported efficiently. A plethora of solutions that achieve
optimal worst-case query time and space have been formulated for this
problem.  The subject of our proposal is, in contrast, to examine the
problem from the perspective of the expected-case. We assume that we are
given the probability of the query point lying in each region and our
goal is to construct a data structure that will minimize the expected
query time. We refer to this problem as expected-case planar point
location.

Referring to Shannon's information-theoretic results, the expected
query time cannot be less than the {\em entropy} defined by the
probability distribution of visiting each polygon of the subdivision,
We denote this entropy by $H$. The aim of the proposal is two-fold. First,
we would like to investigate the existence of planar point location
methods that provide expected query time that asympotically matches the
entropy lower bound and that are practical. Second, we explore the
primarily
theoretical question of whether planar point location is possible in an
expected number of comparisons whose higher order term is exactly $H$,
while using close to linear space. In the one-dimensional case, it is
well-known that at most $H+2$ expected number of comparisons can be
achieved.


Date:				Friday, 19 April 2002

Time:				2:00p.m.-4:00p.m.

Venue:				Room 3311
				Lifts 17-18

Committee Members:		Dr. Sunil Arya (Supervisor)
				Dr. Mordecai Golin (Chairman)
				Dr. Siu-Wing Cheng
				Dr. Rudolf Fleischer


**** ALL are Welcome ****