Date of Award


Publication Type

Master Thesis

Degree Name



Computer Science

First Advisor

Asish Mukhopadhyay


Applied sciences, curve-reconstruction, comparison, certification, resampling



Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.


This thesis work deals with curve reconstruction problem, which contains two parts: experimental comparison and certification.

In the first part we establish the effectiveness of the simple RNG-based algorithm by experimental comparisons with two leading algorithms: the NN-crust and the Conservative-crust. By comparing the outputs of these three algorithms on different samples of increasing complexity, we demonstrate that the RNG-based algorithm performs as well or better.

Since there is no way to verify that a given sample from some unknown curve satisfies the sampling condition, in the second part of this thesis we propose a novel approach that bypasses this problem by certifying to the accuracy of the reconstruction. We smooth the polygonal output of a reconstruction algorithm and sample the smoothed curve. The closeness of the original sample set and resampled set is an indication of the accuracy of the curve-reconstruction algorithm.