Skip to Main content Skip to Navigation
Conference papers

Persistence-sensitive simplication of functions on surfaces in linear time

Dominique Attali 1 Marc Glisse 1 Samuel Hornus 2 Francis Lazarus 1 Dmitriy Morozov 3 
1 GIPSA-GPIG - GIPSA - Géométrie, Perception, Images, Geste
GIPSA-DIS - Département Images et Signal
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Persistence provides a way of grading the importance of homological features in the sublevel sets of a real-valued function. Following the definition given by Edelsbrunner, Morozov and Pascucci, an ε-simplication of a function f is a function g in which the homological noise of persistence less than ε has been removed. In this paper, we give an algorithm for constructing an ε-simplication of a function defined on a triangulated surface in linear time. Our algorithm is very simple, easy to implement and follows directly from the study of the ε-simplication of a function on a tree. We also show that the computation of persistence defined on a graph can be performed in linear time in a RAM model. This gives an overall algorithm in linear time for both computing and simplifying the homological noise of a function f on a surface.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Marc Glisse Connect in order to contact the contributor
Submitted on : Friday, September 20, 2019 - 3:55:34 PM
Last modification on : Thursday, February 3, 2022 - 11:17:47 AM
Long-term archiving on: : Sunday, February 9, 2020 - 4:37:27 AM


Files produced by the author(s)


  • HAL Id : hal-02293165, version 1



Dominique Attali, Marc Glisse, Samuel Hornus, Francis Lazarus, Dmitriy Morozov. Persistence-sensitive simplication of functions on surfaces in linear time. TopoInVis'09, 2009, Salt Lake City, United States. ⟨hal-02293165⟩



Record views


Files downloads