N. Amenta et al., THE CRUST AND THE BETA-SKELETON - COMBINATORIAL CURVE RECONSTRUCTION, Graphical models and image processing, 60(2), 1998, pp. 125-135
We construct a graph on a planar point set, which captures its shape i
n the following sense: if a smooth curve is sampled densely enough, th
e graph on the samples is a polygonalization of the curve, with no ext
raneous edges. The required sampling density varies with the local fea
ture size on the curve, so that areas of less detail can be sampled le
ss densely. We give two different graphs that, in this sense, reconstr
uct smooth curves: a simple new construction which we call the crust,
and the beta-skeleton, using a specific value of beta. (C) 1998 Academ
ic Press.