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

research-article

Homological reconstruction and simplification in R³

Authors:

Dominique Attali,

Olivier Devillers,

André LieutierAuthors Info & Claims

SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometry

Pages 117 - 126

https://doi.org/10.1145/2462356.2462373

Published: 17 June 2013 Publication History

Abstract

We consider the problem of deciding whether the persistent homology group of a simplicial pair (K,L) can be realized as the homology of some complex H_*(X) with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in R³. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S³ within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.

References

[1]

D. Attali, A. Lieutier, and D. Salinas. http://dx.doi.org/10.1016/j.comgeo.2012.02.009Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes. Computational Geometry: Theory and Applications (CGTA), 2012.

Digital Library

[2]

Dominique Attali and André Lieutier. http://dx.doi.org/10.1007/s00454-012--9475--8Optimal reconstruction might be hard. Discrete & Computational Geometry, 49 (2): 133--156, 2013.

Digital Library

[3]

Ulrich Bauer, Carsten Lange, and Max Wardetzky. http://dx.doi.org/10.1007/s00454-011--9350-zOptimal topological simplification of discrete functions on surfaces. Discrete & Computational Geometry, 47 (2): 347--377, 2012.

Digital Library

[4]

Paul Bendich, Herbert Edelsbrunner, Dmitriy Morozov, and Amit Patel. http://dx.doi.org/10.4310/HHA.2013.v15.n1.a3Homology and robustness of level and interlevel sets. Homology, Homotopy and Applications, 15 (1): 51--72, 2013.

[5]

Peter Bubenik and Jonathan A. Scott. http://arxiv.org/abs/1205.3669Categorification of persistent homology. Preprint, 2012. http://arxiv.org/abs/1205.3669patharXiv:1205.3669.

[6]

Frédéric Chazal and André Lieutier. http://dx.doi.org/10.1016/j.comgeo.2007.07.001Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees. Computational Geometry, 40 (2): 156--170, 2008.

Digital Library

[7]

Frédéric Chazal, David Cohen-Steiner, and André Lieutier. http://dx.doi.org/10.1007/s00454-009--9144--8A sampling theory for compact sets in Euclidean space. Discrete & Computational Geometry, 41 (3): 461--479, 2009.

Digital Library

[8]

Frederic Chazal, Vin de Silva, Marc Glisse, and Steve Oudot. http://arxiv.org/abs/1207.3674The structure and stability of persistence modules. Preprint, 2012. http://arxiv.org/abs/1207.3674patharXiv:1207.3674.

[9]

David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. http://dx.doi.org/10.1007/s00454-006--1276--5Stability of persistence diagrams. Discrete & Computational Geometry, 37 (1): 103--120, 2007.

Digital Library

[10]

David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. http://dx.doi.org/10.1007/s10208-008--9027-zExtending persistence using Poincaré and Lefschetz duality. Foundations of Computational Mathematics, 9 (1): 79--103, 2008.

Digital Library

[11]

Vin de Silva and Gunnar Carlsson. http://dx.doi.org/10.2312/SPBG/SPBG04/157--166 Topological estimation using witness complexes. In Eurographics Symposium on Point-Based Graphics, pages 157--166, 2004.

Digital Library

[12]

H. Edelsbrunner. Alpha shapes -- a survey. In R. van de Weygaert, G. Vegter, J. Ritzerveld, and V. Icke, editors, Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings. Springer Verlag. To appear.

[13]

Herbert Edelsbrunner and Michael Kerber. http://dx.doi.org/10.1145/2261250.2261287Alexander duality for functions: the persistent behavior of land and water and shore. In Proceedings of the 2012 symposium on Computational Geometry, pages 249--258. ACM, 2012.

Digital Library

[14]

Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. http://dx.doi.org/10.1007/s00454-002--2885--2Topological persistence and simplification. Discrete & Computational Geometry, 28 (4): 511--533, 2002.

Digital Library

[15]

Herbert Edelsbrunner, Dmitriy Morozov, and Amit Patel. http://dx.doi.org/10.1007/s10208-011--9090--8 Quantifying transversality by measuring the robustness of intersections. Foundations of Computational Mathematics, 11 (3): 345--361, 2011.

Digital Library

[16]

Allen Hatcher. http://www.math.cornell.edu/Ehatcher/AT/ATpage.html Algebraic Topology. Cambridge University Press, 2002.

[17]

Wolfgang Kühnel. Triangulations of manifolds with few vertices. In Franco Tricerri, editor, Advances in differential geometry and topology, pages 59--114. World Scientific, Singapore, 1990.

[18]

Dmitriy Morozov. http://hdl.handle.net/10161/691phHomological Illusions of Persistence and Stability. PhD thesis, Duke University, 2008.

Digital Library

[19]

P. Niyogi, S. Smale, and S. Weinberger. http://dx.doi.org/10.1007/s00454-008--9053--2Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 39 (1--3): 419--441, 2008.

Digital Library

[20]

Edwin H. Spanier. http://www.springer.com/mathematics/geometry/book/978-0--387--94426--5 Algebraic Topology. Springer, 1994.

Cited By

Kissi MPont MLevine JTierny J(2024)A Practical Solver for Scalar Data Topological SimplificationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345634531:1(97-107)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456345
Tierny JFavelier GLevine JGueunet CMichaux M(2018)The Topology ToolKitIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2017.274393824:1(832-842)Online publication date: Jan-2018
https://doi.org/10.1109/TVCG.2017.2743938
Soler MPlainchault MConche BTierny J(2018)Topologically Controlled Lossy Compression2018 IEEE Pacific Visualization Symposium (PacificVis)10.1109/PacificVis.2018.00015(46-55)Online publication date: Apr-2018
https://doi.org/10.1109/PacificVis.2018.00015
Show More Cited By

Index Terms

Homological reconstruction and simplification in R³
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Homological reconstruction and simplification in R 3

We consider the problem of deciding whether the persistent homology group of a simplicial pair ( K , L ) can be realized as the homology H * ( X ) of some complex X with L X K . We show that this problem is NP-complete even if K is embedded in R 3 .As a ...
Computing homology groups of simplicial complexes in R³

Recent developments in analyzing molecular structures and representing solid models using simplicial complexes have further enhanced the need for computing structural information about simplicial complexes in R³. This paper develops basic techniques ...
Extending Persistence Using Poincaré and Lefschetz Duality

Persistent homology has proven to be a useful tool in a variety of contexts, including the recognition and measurement of shape characteristics of surfaces in ź3. Persistence pairs homology classes that are born and die in a filtration of a topological ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometry

June 2013

472 pages

ISBN:9781450320313

DOI:10.1145/2462356

General Chairs:
Guilherme D. da Fonseca
UNIRIO
,
Thomas Lewiner
PUC-Rio
,
Luis Peñaranda
IMPA
,
Program Chairs:
Timothy Chan
University of Waterloo
,
Rolf Klein
University of Bonn

Copyright © 2013 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: 17 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '13

Sponsor:

SoCG '13: Symposium on Computational Geometry 2013

June 17 - 20, 2013

Rio de Janeiro, Brazil

Acceptance Rates

SoCG '13 Paper Acceptance Rate 48 of 137 submissions, 35%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
152
Total Downloads

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

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kissi MPont MLevine JTierny J(2024)A Practical Solver for Scalar Data Topological SimplificationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.345634531:1(97-107)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1109/TVCG.2024.3456345
Tierny JFavelier GLevine JGueunet CMichaux M(2018)The Topology ToolKitIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2017.274393824:1(832-842)Online publication date: Jan-2018
https://doi.org/10.1109/TVCG.2017.2743938
Soler MPlainchault MConche BTierny J(2018)Topologically Controlled Lossy Compression2018 IEEE Pacific Visualization Symposium (PacificVis)10.1109/PacificVis.2018.00015(46-55)Online publication date: Apr-2018
https://doi.org/10.1109/PacificVis.2018.00015
Tierny JTierny J(2018)AbstractionTopological Data Analysis for Scientific Visualization10.1007/978-3-319-71507-0_3(35-66)Online publication date: 18-Jan-2018
https://doi.org/10.1007/978-3-319-71507-0_3
Gyulassy AGunther DLevine JTierny JPascucci V(2014)Conforming Morse-Smale ComplexesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2014.234643420:12(2595-2603)Online publication date: 31-Dec-2014
https://doi.org/10.1109/TVCG.2014.2346434
Tierny JGünther DPascucci V(2014)Optimal General Simplification of Scalar Fields on SurfacesTopological and Statistical Methods for Complex Data10.1007/978-3-662-44900-4_4(57-71)Online publication date: 3-Nov-2014
https://doi.org/10.1007/978-3-662-44900-4_4

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.

Media

Figures

Other

Tables

View Table of Contents