Given a set of points in a metric space, a fundamental problem is to preprocess these points for answering nearest-neighbor queries on them. Proximity search is the problem of answering more general queries that need the first, second, or further closest neighbors of a query point, possibly in spaces where a separation function is defined which may be more general than a metric. In this thesis, we look at several proximity search problems. Our goal is to better understand, when proximity search is easy, i.e., there is a data-structure requiring near-linear space and allowing logarithmic query time. We study three problems:(i) Answering nearest-neighbor queries in a metric space when the query is restricted to a subspace of low doubling dimension. We show that even though the points lie in a high dimensional ambient space, the problem is inherently low dimensional.(ii) Answering kth nearest-neighbor queries in Euclidean space. We provide a sub-linear space data- structure for this problem. We also extend this to the case when the data points are replaced by disjoint balls (of arbitrary radii), and the distance of a query point to a ball is the distance to the ball as a set.(iii) We consider more general distance functions and proximity search queries on them. This translates to the abstract problem of computing the lower envelope of a set of functions, for a query point. For this abstract problem, we provide a set of sufficient conditions that allow efficient data-structures for computation of the lower envelope. We apply this to several problems of interest. Among new results, we provide approximate weighted Voronoi diagrams in low dimensional Euclidean space.
PDF
download
878987797
028-85220240
