A fast algorithm for well-spaced points and approximate delaunay graphs
Gary Lee Miller, Donald R. Sheehy, Ameya Velingker · 2013
We present a new algorithm that produces a well-spaced superset of points conforming to a given input set in any dimension with guaranteed optimal output size. We also provide an approximate Delaunay graph on the output points. Our algorithm runs in expected time O(2O(d)(n log n + m)), where n is the input size, m is the output point set size, and d is the ambient dimension. The constants only depend on the desired element quality bounds.