Curve Reconstruction: Given a set of samples from a curve
we wish to compute a polygonal reconstruction of the curve, i.e., points
should be joined by edges in the order they appear on the curve.
Reconstruction of smooth curves: NN-crust
We provide a very simple nearest neighbor algorithm for reconstructing smooth curves. The algorithm works in any dimension for curve reconstruction. We show a reconstructed curve in 3D below.
T. K. Dey and P.
simple provable algorithm for curve reconstruction .
Proc. 10th. ACM-SIAM Symposium on Discrete Algorithms (SODA '99) 1999,
A reconstructed curve in 3D
Also check PROGRAM implemented at MPI, Germany.
Reconstruction of curves with or without boundary: Conservative-crust
Smooth curves with boundary points need special attention since the usual methods such as crust and NN-crust cannot handle such curves. We devise an algorithm for reconstructing curves with boundary points.
T. K. Dey, K. Mehlhorn and E. Ramos. Curve reconstruction: connecting dots with good reason . Comput. Geom. Theiry & Appl., Vol. 15 (2000), 229-244. Also in Proc. 15th. Sympos. Computational Geometry 1999, 197--206.
Reconstruction of curves with corners: Gathan
Nonsmooth curves pose problem for curve reconstruction. The sampling condition required by crust and all other algorithms with guarantee cannot be satisfied near corners. We designed an algorithm to handle curves with corners.
T. K. Dey and R. Wenger. Reconstructing curves with sharp corners. Computational Geometry Theory Applications, vol 19, 2001, 89--99.
T. K. Dey and R. Wenger. Fast reconstruction of curves with sharp corners. Computational Geometry Theory Applications, 2002, to appear.
this program (guaranteed reconstruction) implemented by R. Wenger