PhD Qualifying Examination


"Approximate Geometric Searching"

Mr. Jian Xia


Abstract:

Geometric searching problems such as nearest neighbor searching and range
searching are fundamental problems in computational geometry. In these
problems, we have to preprocess the given point set into a data structure
according to the query type so that the query can be answered efficiently.
To achieve the simultaneous goals of roughly linear space and logarithmic
query time, we consider the approximate versions of these searching
problems, in which it is allowed to return the approximate answer within a
specified error. Approximate geometric searching is also widely used in
many applications, which need fast query time and can tolerate small error
within the guarantee. In the survey, we review some data structures and
the main techniques in this area.


Date:     		Monday, 27 February 2006

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

Venue:                  Room 3301
			lifts 17-18

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


**** ALL are Welcome ****