$k$th Nearest Neighbor Sampling in the Plane
Kirk Gardner, and Donald R. Sheehy
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}}