Neighborhood finders and nearest neighbor queries are fundamental components of sampling-based motion planning (SBMP) algorithms. Using different distance metrics or otherwise changing the definition of a neighborhood produces different algorithms with unique empirical and theoretical properties. In his textbook on planning algorithms, LaValle suggests a neighborhood finder for the Rapidly-exploring Random Tree (RRT) algorithm, which finds the nearest neighbor of the sampled point on theswathof the tree, that is, on the set of all of the points on the tree edges, using a hierarchical data structure. In this paper, we implement such a neighborhood finder and show, theoretically and experimentally, that this results in more efficient algorithms.

We study colored coverage and clustering problems. Here, we are given a colored point set where the points are covered by (unknown) $k$ clusters, which are monochromatic (i.e., all the points covered by the same cluster, have the same color). The access to the colors of the points (or even the points themselves) is provided indirectly via various queries (such as nearest neighbor, or separation queries). We show that if the number of clusters is a constant, then one can correctly deduce the color of all the points (i.e., compute a monochromatic clustering of the points) using a polylogarithmic number of queries. We investigate several variants of this problem, including Undecided Linear Programming, covering of points by $k$ monochromatic balls, covering by $k$ triangles/simplices, and terrain simplification. For the later problem, we present the first near linear time approximation algorithm. While our approximation is slightly worse than previous work, this is the first algorithm to have subquadratic complexity if the terrain has "small" complexity.