Optimal reconstruction might be hard

DOI10.1007/s00454-012-9475-8zbMath1261.68120OpenAlexW1993472517MaRDI QIDQ1943654

Dominique Attali, André Lieutier

Publication date: 20 March 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-012-9475-8

zbMATH Keywords

NP-completenessshape reconstructionsampling conditionstopological persistence3SAThomological simplification

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Compensated Convexity, Multiscale Medial Axis Maps and Sharp Regularity of the Squared-Distance Function ⋮ Homological reconstruction and simplification in \(\mathbb{R}^3\)

Uses Software

• Powercrust

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stability of persistence diagrams
• A sampling theory for compact sets in Euclidean space
• \(r\)-regular shape reconstruction from unorganized points
• Smooth surface reconstruction via natural neighbour interpolation of distance functions
• Surface reconstruction by Voronoi filtering
• Topological persistence and simplification
• Stability and computation of topological invariants of solids in \({\mathbb R}^n\)
• Finding the homology of submanifolds with high confidence from random samples
• A simple algorithm for homeomorphic surface reconstruction
• Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based surface reconstruction
• Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes
• Reconstructing shapes with guarantees by unions of convex sets
• The power crust, unions of balls, and the medial axis transform