License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.9
URN: urn:nbn:de:0030-drops-160170
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16017/
Bakke Bjerkevik, Håvard
Tighter Bounds for Reconstruction from ε-Samples
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.
BibTeX - Entry
@InProceedings{bakkebjerkevik:LIPIcs.SoCG.2022.9,
author = {Bakke Bjerkevik, H\r{a}vard},
title = {{Tighter Bounds for Reconstruction from \epsilon-Samples}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {9:1--9:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16017},
URN = {urn:nbn:de:0030-drops-160170},
doi = {10.4230/LIPIcs.SoCG.2022.9},
annote = {Keywords: Curve reconstruction, surface reconstruction, \epsilon-sampling}
}
|
Keywords: |
|
Curve reconstruction, surface reconstruction, ε-sampling |
|
Collection: |
|
38th International Symposium on Computational Geometry (SoCG 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.06.2022 |
