More Web Proxy on the site http://driver.im/

research-article

Optimal reconstruction might be hard

Authors:

Dominique Attali,

André LieutierAuthors Info & Claims

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

Pages 334 - 343

https://doi.org/10.1145/1810959.1811014

Published: 13 June 2010 Publication History

Abstract

Sampling conditions for recovering the homology of a set using topological persistence are much weaker than sampling conditions required by any known polynomial time algorithm for producing a topologically correct reconstruction. Under the former sampling conditions which we call weak sampling conditions, we give an algorithm that outputs a topologically correct reconstruction. Unfortunately, even though the algorithm terminates, its time complexity is unbounded. Motivated by the question of knowing if a polynomial time algorithm for reconstruction exists under the weak sampling conditions, we identify at the heart of our algorithm a test which requires answering the following question: given two 2-dimensional simplicial complexes L ⊂ K, does there exist a simplicial complex containing L and contained in K which realizes the persistent homology of L into K? We call this problem the homological simplification of the pair (K, L) and prove that this problem is NP-complete, using a reduction from 3SAT.

References

[1]

N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete and Computational Geometry, 22(4):481--504, 1999.

[2]

N. Amenta, M. Bern, and D. Eppstein. The crust and the β-skeleton: Combinatorial curve reconstruction. Graphical Models and Image Processing, 60(2):125--135, 1998.

Digital Library

[3]

N. Amenta, S. Choi, T. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. In Proceedings of the sixteenth annual symposium on Computational geometry, pages 213--222. ACM New York, NY, USA, 2000.

Digital Library

[4]

N. Amenta, S. Choi, and R. Kolluri. The power crust, unions of balls, and the medial axis transform. Computational Geometry: Theory and Applications, 19(2-3):127--153, 2001.

Digital Library

[5]

D. Attali. r-regular shape reconstruction from unorganized points. Computational Geometry: Theory and Applications, 10:239--247, 1998.

Digital Library

[6]

D. Attali, M. Glisse, S. Hornus, F. Lazarus, and D. Morozov. Persistence-sensitive simplification of functions on surfaces in linear time. Manuscript, INRIA, 2008.

[7]

D. Attali and A. Lieutier. Reconstructing shapes with guarantees by unions of convex sets. http://hal.archives-ouvertes.fr/hal-00427035/en/.

Digital Library

[8]

D. Attali and A. Lieutier. Reconstructing shapes with guarantees by unions of convex sets. In Proc. ACM Symposium on Computational Geometry, 2010. Submitted.

Digital Library

[9]

J. Boissonnat and F. Cazals. Smooth surface reconstruction via natural neighbour interpolation of distance functions. Computational Geometry: Theory and Applications, 22(1-3):185--203, 2002.

Digital Library

[10]

J. Boissonnat, L. Guibas, and S. Oudot. Manifold reconstruction in arbitrary dimensions using witness complexes. Discrete and Computational Geometry, 42(1):37--70, 2009.

Digital Library

[11]

J. Boissonnat and S. Oudot. Provably good sampling and meshing of Lipschitz surfaces. In Proceedings of the twenty-second annual symposium on Computational geometry, page 346. ACM, 2006.

Digital Library

[12]

F. Chazal, D. Cohen-Steiner, and A. Lieutier. A sampling theory for compact sets in Euclidean space. Discrete and Computational Geometry, 41(3):461--479, 2009.

Digital Library

[13]

F. Chazal, D. Cohen-Steiner, A. Lieutier, and B. Thibert. Shape smoothing using double offsets. In Proc. of the ACM symposium on Solid and physical modeling, pages 183--192. ACM New York, NY, USA, 2007.

Digital Library

[14]

F. Chazal and A. Lieutier. Stability and computation of topological invariants of solids in R ⁿ Discrete and Computational Geometry, 37(4):601--617, 2007.

Digital Library

[15]

F. Chazal and S. Oudot. Towards persistence-based reconstruction in Euclidean spaces. In Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 232--241. ACM, 2008.

Digital Library

[16]

F. Clarke. Optimization and nonsmooth analysis. Society for Industrial Mathematics, 1990.

[17]

D. Cohen-Steiner. Personal communication. 2008.

[18]

D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discrete and Computational Geometry, 37(1):103--120, 2007.

Digital Library

[19]

T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to algorithms, 2001.

Digital Library

[20]

V. de Silva. Personal communication. 2009.

[21]

V. de Silva and G. Carlsson. Topological estimation using witness complexes. Proc. Sympos. Point-Based Graphics, pages 157--166, 2004.

Digital Library

[22]

T. Dey, S. Funke, and E. Ramos. Surface reconstruction in almost linear time under locally uniform sampling. In Abstracts 17th European Workshop Comput. Geom, pages 129--132. Citeseer, 2001.

[23]

T. Dey, J. Giesen, E. Ramos, and B. Sadri. Critical points of the distance to an epsilon-sampling of a surface and ow-complex-based surface reconstruction. In Proc. of the twenty-first annual symposium on Computational geometry, page 227. ACM, 2005.

Digital Library

[24]

T. Dey and S. Goswami. Provable surface reconstruction from noisy samples. Computational Geometry: Theory and Applications, 35(1-2):124--141, 2006.

Digital Library

[25]

T. Dey and K. Li. Cut locus and topology from surface point data. In Proceedings of the 25th annual symposium on Computational geometry, pages 125--134. ACM New York, NY, USA, 2009.

Digital Library

[26]

H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete and Computational Geometry, 28(4):511--533, 2002.

Digital Library

[27]

H. Edelsbrunner, D. Morozov, and V. Pascucci. Persistence-sensitive simplification functions on 2-manifolds. In Proceedings of the twenty-second annual symposium on Computational geometry, page 134. ACM, 2006.

Digital Library

[28]

K. Grove. Critical point theory for distance functions. In Proc. of Symposia in Pure Mathematics, volume 54, pages 357--386, 1993.

[29]

A. Lieutier. Any open bounded subset of R n has the same homotopy type as its medial axis. Computer-Aided Design, 36(11):1029--1046, 2004.

Digital Library

[30]

D. Morozov. Homological Illusions of Persistence and Stability. Ph.D. Dissertation, Duke University, 2008.

Digital Library

[31]

J. Munkres. Elements of algebraic topology. Perseus Books, 1993.

[32]

P. Niyogi, S. Smale, and S. Weinberger. Finding the Homology of Submanifolds with High Confidence from Random Samples. Discrete Computational Geometry, 39(1-3):419--441, 2008.

Digital Library

[33]

S. Oudot. Echantillonnage et maillage de surfaces avec garanties. Ph.D. Dissertation, Ecole Polytechnique, 2005.

Cited By

Attali DLieutier AKirkpatrick DMitchell J(2010)Reconstructing shapes with guarantees by unions of convex setsProceedings of the twenty-sixth annual symposium on Computational geometry10.1145/1810959.1811015(344-353)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1810959.1811015

Index Terms

Optimal reconstruction might be hard
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Optimal Reconstruction Might be Hard

Given as input a point set $$\mathcal S $$ that samples a shape $$\mathcal A $$, the condition required for inferring Betti numbers of $$\mathcal A $$ from $$\mathcal S $$ in polynomial time is much weaker than the conditions required by any known ...
Clique-width minimization is NP-hard
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic with second-order quantification on vertex sets, that includes NP-hard problems) ...
On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

June 2010

452 pages

ISBN:9781450300162

DOI:10.1145/1810959

Program Chairs:
David Kirkpatrick
University of British Columbia, Canada
,
Joseph Mitchell
SUNY Stony Brook, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '10

Sponsor:

SoCG '10: Symposium on Computational Geometry

June 13 - 16, 2010

Utah, Snowbird, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
101
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Attali DLieutier AKirkpatrick DMitchell J(2010)Reconstructing shapes with guarantees by unions of convex setsProceedings of the twenty-sixth annual symposium on Computational geometry10.1145/1810959.1811015(344-353)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1810959.1811015

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten