A Simple Provable Algorithm for Curve Reconstruction
Tamal K. Dey, Piyush Kumar · 1999
We present an algorithm that provably reconstructs a curve in the framework introduced by Amenta, Bern and Eppstein. The highlights of the algorithm are: (i) it is simple, (ii) it requires a sampling density better than previously known, (iii) it can be adapted for curve reconstruction in higher dimensions straightforwardly. 1 Introduction We consider the problem of curve reconstruction that takes a set of sample points on a smooth closed curve C, and requires to produce a geometric graph G having exactly those edges that connect sample points adjacent in C. Obviously, given only the samples, it is not always possible to compute G unless some additional conditions are satisfied by the input. Amenta, Bern and Eppstein [1] proposed a framework based on local feature size under which they show two graphs, crust and fi-skeleton, coincide with G if the points are sufficiently sampled. Some of the other effective approaches include ff-shapes by [6] which is analyzed later by [3], r-reg...