Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Curve Reconstruction the Traveling Salesman Problem
Joachim Giesen, ETH Zurich
An instance of the curve reconstruction problem is given by a finite sample of an unknown curve. The task is to construct a polygon which connects the sample points in the same order as they are connected on the unknown curve.
Of course there is no algorithm that works for any curve and any sample. Today there are a number of methods known that work for simple smooth curves and sufficiently dense samples. All these methods do not work for non smooth curves, i.e. polygons. We show that the Traveling Salesman Tour / Path solves the reconstruction problem for (closed) simple curves and sufficiently dense
samples under weak regularity assumptions (in every point of the curve left and right tangents have to exist and in every point these tangents do not point in opposite directions). Althaus and Mehlhorn were able to show that under the same assumptions (dense sample, regularity) the Traveling Salesman Tour can be computed in polynomial time. It turned out the the TSP-based reconstruction works very well in practice (see: http://review.mpi-sb.mpg.de:81/Curve-Reconstruction/ ).
Back
