Curve reconstruction: Connecting dots with good reason. (English) Zbl 0955.68113

Summary: Curve reconstruction algorithms are supposed to reconstruct curves from point samples. Recent papers present algorithms that come with a guarantee: Given a sufficiently dense sample of a closed smooth curve, the algorithms construct the correct polygonal reconstruction. Nothing is claimed about the output of the algorithms, if the input is not a dense sample of a closed smooth curve, e.g., a sample of a curve with endpoints. We present an algorithm 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 justifies \(G\) as the reconstruction from \(P\).


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI