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},
  Pages = {34--41},
	Year = {2016}}