| LEP: Curve Reconstruction |
|
History Demo Information Download Friends
Contact Algorithmic Solutions Software GmbH News Reviews |
- Curve Reconstruction Algorithms
|
|
|
-
If you want to get update information concerning this package please contact
althaus@mpi-sb.mpg.de
to be put on a mailing list.
|
|
Ernst Althaus
MPI Informatik Im Stadtwald 66123 Saarbrücken Germany email: althaus@mpi-sb.mpg.de |
-
An instance of the curve reconstruction problem is a finite sample $V$ of an
unknown curve $\gamma$. The task is to connect the points in $V$ in the
order in which they lie on $\gamma$. Several new algorithms for the curve
reconstruction problem have been proposed in recent years. All algorithms
compute a subgraph of the Delaunay triangulation of $V$. Most algorithms make
the decisions of which edges to put into the reconstructions locally and run in
time $O(n \log n)$ worst case, one algorithm uses a global criterion and
computes the traveling salesman tour of $V$. Our implementation of this
algorithm has exponential worst case running time.
Our experiments show that
the TSP-algorithm is far superior with respect to reconstruction quality.
In our experiments its running time was never more than 13 times the running
time of the fastest of
the other algorithms.
|
|
|
back to the LEDA EP index page