Item

Abstract

An instance of the curve reconstruction problem is a finite sample set $V$ of an
unknown curve $\gamma$. The task is to connect the points in $V$ in the
order in which they lie on $\gamma$. Giesen~\cite{Giesen:TSP} showed recently
that the Traveling Salesman tour of $V$ solves the reconstruction problem under
fairly week assumptions on $\gamma$ and $V$. We extend his result along three
dimensions. We weaken the assumptions, give an alternate proof, and
show that in the context of curve reconstruction,
the Traveling Salesman tour can be constructed in polynomial time.