Curve Reconstruction with Many Fewer Samples (SGP'16 Test Talk)

We consider the problem of sampling points from a collection of smooth curves in the plane, such that proximity-based curve reconstruction can rebuild the curves. Reconstruction requires dense sampling of local features, i.e., curve intervals which are close in Euclidean distance but far apart geodesically. We first show a tighter bound ε < 0.6-sampling that permits our proposed algorithm to reconstruct the curve and requires many fewer samples than state-of-the-art ε < 1/3-sampling. We also present a new sampling scheme which reduces the required density even further than ε < 0.6-sampling. We achieve this by better controlling the spacing between geodesically consecutive points. Our novel sampling condition is based on the minimum local feature size along intervals between samples. This is mathematically closer to the reconstruction density requirements, particularly near sharp-angled features. We prove a lower and upper bound for the required samples for ρ-sampling in terms of ε-sampling and show that it cuts the required number of samples for the reconstruction more than half for typical examples.