NEW RESULTS IN NEAREST NEIGHBOR AND RANGE SEARCHING

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence

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

By

Mr. Jian Xia


Abstract

In this thesis, we 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. 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. 
We consider this problem in a weighted setting, where each point is associated 
with a weight from a commutative semigroup, and the output of the query is the 
semigroup sum of the weights of the points lying within the halfspace. We 
establish two new lower bounds for this problem. Neglecting logarithmic 
factors, our result for integral semigroups matches the best known upper bound 
due to Matoušek. Our result for general semigroups improves upon the best known 
lower bound due to Brönnimann, Chazelle, and Pach. Moreover, it also resolves 
the computational complexity of halfspace range searching over idempotent 
semigroups in the important special case of uniformly distributed point sets.


Date:			Tuesday, 4 May 2010

Time:			10:00am – 12:00noon

Venue:			Room 3494
 			Lifts 25/26

Chairman:		Prof. Howard Luong (ECE)

Committee Members:	Prof. Sunil Arya (Supervisor)
 			Prof. Mordecai Golin
                  	Prof. Ke Yi
                         Prof. Ajay Joneja (IELM)
                         Prof. Rudolf Fleischer (Comp. Sci., Fudan Univ.)


**** ALL are Welcome ****