$k$th Nearest Neighbor Sampling in the Plane

CCCG: The Canadian Conference in Computational Geometry
2016

Let $B$ be a square region in the plane.
We give an efficient algorithm that takes a set $P$ of $n$ points from $B$, and produces a set $M\subset B$ with the property that the distance to the second nearest point in $M$ approximates the distance to the $k$th nearest point of $P$.
That is, there are constants $\alpha, \beta\in \mathbb{R}$ such that for all $x\in B$, we have $\alpha\mathrm{d}_{P,k}(x) \le \mathrm{d}_{M,2}(x) \le \beta \mathrm{d}_{P,k}(x)$, where $\mathrm{d}_{M,2}$ and $\mathrm{d}_{P,k}$ denote the second nearest and $k$th nearest neighbor distance functions to $M$ and $P$ respectively.
The algorithm is based on Delaunay refinement.
The output set $M$ also has the property that its Delaunay triangulation has a lower bound on the size of the smallest angle.
The primary application is in statistical density estimation and robust geometric inference.

@inproceedings{gardner16kth, Author = {Kirk P. Gardner and Donald R. Sheehy}, Booktitle = {Proceedings of the Canadian Conference on Computational Geometry}, Title = {$k$th Nearest Neighbor Sampling in the Plane}, Year = {2016}}