Tighter Bounds for Reconstruction from ε-samples

2021/12/07 by Håvard Bakke Bjerkevik, Bjerkevik, Håvard Bakke
Computer Science · Medicine · #Computational Geometry (cs.CG) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Medical Image Segmentation Techniques #Medical Imaging Techniques and Applications #Metric Geometry (math.MG)

paper · pdf · doi:10.48550/arxiv.2112.03656

openalex publication_date 2021/12/07 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28

Abstract

We show that reconstructing a curve in ℝ^d for d≥ 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 ℝ² and (1)/(3)-samples in ℝ^d for d≥ 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.

Related

• Reconstructing Curves from Points and Tangents
• Novel resolution analysis for the Radon transform in \mathbb R² for functions with rough edges
• Sampling theorems for inverse problems on Riemannian manifolds
• Method of Moments for Estimation of Noisy Curves
• Deterministic guarantees for L¹-reconstruction: A large sieve approach with geometric flexibility