Tighter Bounds for Reconstruction from $\epsilon$-samples

Abstract

We show that reconstructing a curve in ${\mathbb{R}}^d$ for $d\ge 2$ from a $0.66$-sample is always possible using an algorithm similar to the classical NN-Crust algorithm. Previously, this was only known to be possible for $0.47$-samples in ${\mathbb{R}}^2$ and $\frac{1}{3}$-samples in ${\mathbb{R}}^d$ for $d\ge 3$. In addition, we show that there is not always a unique way to reconstruct a curve from a $0.72$-sample; this was previously only known for $1$-samples. We also extend this non-uniqueness result to hypersurfaces in all higher dimensions.

24 pages, 16 figures. Full version of paper to be published in SoCG proceedings