Curve reconstruction: Connecting dots with good reason

Curve reconstruction algorithms are supposed to reconstruct curves from poi nt samples. Recent papers present algorithms that come with a guarantee: Gi ven a sufficiently dense sample of a closed smooth curve, the algorithms co nstruct the correct polygonal reconstruction, Nothing is claimed about the output of the algorithms, if the input is not a dense sample of a closed sm ooth curve, e.g., a sample of a curve with endpoints. We present an algorit hm that comes with a guarantee for any set P of input points. The algorithm constructs a polygonal reconstruction G and a smooth curve Gamma that just ifies G as the reconstruction from P. (C) 2000 Elsevier Science B.V. All ri ghts reserved.