Homological reconstruction and simplification in R3

Dominique Attali; Ulrich Bauer; Olivier Devillers; Marc Glisse; André Lieutier

hal-00761208, version 1

Homological reconstruction and simplification in R3

Dominique Attali () ¹, Ulrich Bauer () ², Olivier Devillers (, ) ³, Marc Glisse ()^a^, 3, André Lieutier ⁴

N° RR-8169 (2012)

Abstract: 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 R3. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S3 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-complete.

a – INRIA
1: Grenoble Images Parole Signal Automatique (GIPSA-lab)
CNRS : UMR5216 – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – Université Stendhal - Grenoble III – Institut Polytechnique de Grenoble - Grenoble Institute of Technology
2: Institute of Science and Technology [Austria] (IST Austria)
IST Austria
3: GEOMETRICA (INRIA Sophia Antipolis / INRIA Saclay - Ile de France)
INRIA
4: Dassault Systèmes
Dassault Systèmes

hal-00761208, version 1
http://hal.inria.fr/hal-00761208
oai:hal.inria.fr:hal-00761208
From: Olivier Devillers <>
Submitted on: Wednesday, 5 December 2012 10:09:35
Updated on: Wednesday, 5 December 2012 11:24:14

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="hal-00761208"><monogr>
<author><persName><forename>Dominique</forename><surname>Attali</surname></persName>
<affiliation>
<orgName type="laboratory">GIPSA-lab</orgName>
<orgName type="team">Grenoble Images Parole Signal Automatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5216</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
<orgName type="institution">Université Stendhal - Grenoble III</orgName>
<orgName type="institution">Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
</affiliation>
</author>
<author><persName><forename>Ulrich</forename><surname>Bauer</surname></persName>
<affiliation>
<orgName type="laboratory">IST Austria</orgName>
<orgName type="team">Institute of Science and Technology [Austria]</orgName>
<country>AT</country>
<orgName type="institution">IST Austria</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Devillers</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / INRIA Saclay - Ile de France</orgName>
<orgName type="team">GEOMETRICA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Marc</forename><surname>Glisse</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / INRIA Saclay - Ile de France</orgName>
<orgName type="team">GEOMETRICA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>André</forename><surname>Lieutier</surname></persName>
<affiliation>
<orgName type="team">Dassault Systèmes</orgName>
<country>FR</country>
<orgName type="institution">Dassault Systèmes</orgName>
</affiliation>
</author>
<title type="main" level="m">Homological reconstruction and simplification in R3</title><title type="main" level="m">Homological reconstruction and simplification in R3</title><imprint><biblScope type="publicationDate">2012-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/hal-00761208</idno><idno type="HALFile">http://hal.inria.fr/hal-00761208/PDF/RR-8169.pdf</idno></biblStruct>
</listBibl>
</listBibl>