The crust and the beta-skeleton: combinatorial curve reconstruction.
N. Amenta,
M. Bern,
and D. Eppstein.
Graphical Models & Image Processing 60/2 (2): 125–135, 1998, doi:10.1006/gmip.1998.0465.
We consider the problem of "connect the dots": if we have an unknown smooth curve from which sample points have been selected, we would like to find a curve through the sample points that approximates the unknown curve. We show that if the local sample density is sufficiently high, a simple algorithm suffices: form the Delaunay triangulation of the sample points together with their Voronoi vertices, and keep only those Delaunay edges connecting original sample points. There have been many follow-up papers suggesting alternative methods, generalizing the problem to the reconstruction of curves with sharp corners or to curves and surfaces in higher dimensions, etc.