In geometric range searching, algorithmic problems of the following type are considered.
Given an n-point set P in the plane, build a data structure so that, given a query triangle R …

The nearest neighbor problem is the follolving: Given a set of n points P=(PI,..., p,} in some
metric space X, preprocess P so as to efficiently answer queries which require finding bhe …

During the last decade, incremental sampling-based motion planning algorithms, such as
the Rapidly-exploring Random Trees (RRTs), have been shown to work well in practice and …

Consider a set of S of n data points in real d-dimensional space, Rd, where distances are
measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into …

We consider the computational problem of nding nearest neighbors in general metric
spaces. Of particular interest are spaces that may not be conveniently embedded or …

This book is primarily a textbook introduction to various areas of discrete geometry. In each
area, it explains several key results and methods, in an accessible and concrete manner. It …

We show an optimal data-dependent hashing scheme for the approximate near neighbor
problem. For an n-point dataset in a d-dimensional space our data structure achieves query …

Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality Page 1
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality The MIT …

Random sampling is used for several new geometric algorithms. The algorithms are “Las
Vegas,” and their expected bounds are with respect to the random behavior of the …

We present a new technique for half-space and simplex range query using Ο (n) space and
Ο (na) query time, where a< d (d-1)/d (d-1)+ 1+ γ for all dimensions d≥ 2 and γ> 0. These …