Speaker: Stefan Ohrhallinger (E193-02)
Curve reconstruction from unstructured points in a plane is a fundamental problem with many
applications that has generated research interest for decades. Involved aspects like handling open,
sharp, multiple and non-manifold outlines, runtime and provability as well as its extension to 3D
for surface reconstruction have led to many different algorithms. This thesis spans a wide range,
starting from improved interpolation of manifold curves over fitting noisy points with better
accuracy. Then it shows how to require fewer points for successful reconstruction and proves the
lower limit of required samples with regard to local feature size. Further, statistical accuracy for
noise-infected samples is proved. A new sampling condition is introduced that can be expressed as
a simple function of the long-standing epsilon-sampling, and permits to reconstruct curves with
even fewer samples. As a side product, an algorithm for sampling curves is designed as well. A
survey paper compares this body of work with all related work in this now mature field and
includes an open source benchmark that allows to easily evaluate competing algorithms in multiple
aspects and highlights their relative strengths. Finally, for a selected 2D algorithm, an extension to
3D is demonstrated. In summary, this thesis covers guarantees, backed up by proofs, for
reconstruction of curves in 2D, and offers many novel perspectives for surface reconstruction in
3D, where several important open problems remain.
