



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: NNcrust 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.
Kumar. A
simple provable algorithm for curve reconstruction .
Proc. 10th. ACMSIAM Symposium on Discrete Algorithms (SODA '99) 1999,
893894
A reconstructed curve in 3D Also check PROGRAM implemented at MPI, Germany. Reconstruction of curves with or without boundary: Conservativecrust Smooth curves with boundary
points need special attention since the usual methods such as crust
and NNcrust 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), 229244. Also in Proc. 15th. Sympos. Computational Geometry 1999, 197206.
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, 8999. T. K. Dey and R. Wenger. Fast reconstruction of curves with sharp corners. Computational Geometry Theory Applications, 2002, to appear.
Download
this program (guaranteed reconstruction) implemented by R. Wenger
Examples
