Curve Reconstruction

of an unknown curve and the task is to connect the points in the
sample in the order in which they lie on the curve. The aim is
find algorithms which come ith a reconstruction and a performance
guarantee: For curves from a certain class of curves and a sample
set satisfying a certain sampling condition, the algorithm is
guaranteed to find the reconstruction. The algorithm should also
be efficient. We report on recent advances on the problem. These
recent results combine methods from computational geometry and
combinatorial optimization.