中文繁體 |
中文简体
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 ****
