NEW RESULTS IN NEAREST NEIGHBOR AND RANGE SEARCHING

PhD Thesis Proposal Defence


Title: "NEW RESULTS IN NEAREST NEIGHBOR AND RANGE SEARCHING"

by

Mr. Jian XIA


Abstract:

In this thesis, we propose to tackle challenging open questions in the area of 
nearest neighbor and range searching. Nearest neighbor and range searching are 
among the most fundamental problems in computational geometry, with numerous 
applications in areas such as pattern recognition, machine learning, and 
information retrieval. In these problems, we have to preprocess the given point 
set in some space into a data structure according to the query type, so that 
queries can be answered efficiently. So far in our research, we have obtained 
the following three results.

Our first two results concern approximate nearest neighbor searching in the 
context of metric spaces. We show that the concept of approximate Voronoi 
diagram (AVD), which is known to provide the most efficient solution in 
Euclidean spaces, can be generalized to doubling spaces as well as to 
hyperbolic spaces. This enables us to achieve much faster query times than 
previously possible, and also achieve space-time tradeoffs for the first time.

Our third result is concerned with the complexity of halfspace range searching 
in Euclidean space. We show that the lower bound established by Brönnimann, 
Chazelle and Pach can be significantly improved. Our lower bound applies to 
uniformly distributed points, and it matches the upper bound by Fonseca and 
Mount for this distribution.

In our future research, we will try to simplify our AVD constructions. We will 
also consider the issue of construction time in detail. Regards the halfspace 
range searching problem, despite our improvements, there still remains a 
significant gap between the known upper and lower bounds, which we will 
continue to investigate.


Date:     		Monday, 16 November 2009

Time:                   2:00pm - 4:00pm

Venue:                  Room 4483
 			lifts 25/26

Committee Members:      Dr. Sunil Arya (Supervisor)
 			Prof. Siu-Wing Cheng (Chairperson)
 			Prof. Mordecai Golin
 			Dr. Ke Yi


**** ALL are Welcome ****