---
_id: '1072'
abstract:
- lang: eng
text: Given a finite set of points in Rn and a radius parameter, we study the Čech,
Delaunay–Čech, Delaunay (or alpha), and Wrap complexes in the light of generalized
discrete Morse theory. Establishing the Čech and Delaunay complexes as sublevel
sets of generalized discrete Morse functions, we prove that the four complexes
are simple-homotopy equivalent by a sequence of simplicial collapses, which are
explicitly described by a single discrete gradient field.
acknowledgement: This research has been supported by the EU project Toposys(FP7-ICT-318493-STREP),
by ESF under the ACAT Research Network Programme, by the Russian Government under
mega project 11.G34.31.0053, and by the DFG Collaborative Research Center SFB/TRR
109 “Discretization in Geometry and Dynamics”.
article_processing_charge: No
article_type: original
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Bauer U, Edelsbrunner H. The Morse theory of Čech and delaunay complexes. Transactions
of the American Mathematical Society. 2017;369(5):3741-3762. doi:10.1090/tran/6991
apa: Bauer, U., & Edelsbrunner, H. (2017). The Morse theory of Čech and delaunay
complexes. Transactions of the American Mathematical Society. American
Mathematical Society. https://doi.org/10.1090/tran/6991
chicago: Bauer, Ulrich, and Herbert Edelsbrunner. “The Morse Theory of Čech and
Delaunay Complexes.” Transactions of the American Mathematical Society.
American Mathematical Society, 2017. https://doi.org/10.1090/tran/6991.
ieee: U. Bauer and H. Edelsbrunner, “The Morse theory of Čech and delaunay complexes,”
Transactions of the American Mathematical Society, vol. 369, no. 5. American
Mathematical Society, pp. 3741–3762, 2017.
ista: Bauer U, Edelsbrunner H. 2017. The Morse theory of Čech and delaunay complexes.
Transactions of the American Mathematical Society. 369(5), 3741–3762.
mla: Bauer, Ulrich, and Herbert Edelsbrunner. “The Morse Theory of Čech and Delaunay
Complexes.” Transactions of the American Mathematical Society, vol. 369,
no. 5, American Mathematical Society, 2017, pp. 3741–62, doi:10.1090/tran/6991.
short: U. Bauer, H. Edelsbrunner, Transactions of the American Mathematical Society
369 (2017) 3741–3762.
date_created: 2018-12-11T11:49:59Z
date_published: 2017-05-01T00:00:00Z
date_updated: 2023-09-20T12:05:56Z
day: '01'
department:
- _id: HeEd
doi: 10.1090/tran/6991
ec_funded: 1
external_id:
arxiv:
- '1312.1231'
isi:
- '000398030400024'
intvolume: ' 369'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1312.1231
month: '05'
oa: 1
oa_version: Preprint
page: 3741 - 3762
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Transactions of the American Mathematical Society
publication_status: published
publisher: American Mathematical Society
publist_id: '6311'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Morse theory of Čech and delaunay complexes
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 369
year: '2017'
...
---
_id: '1424'
abstract:
- lang: eng
text: We consider the problem of statistical computations with persistence diagrams,
a summary representation of topological features in data. These diagrams encode
persistent homology, a widely used invariant in topological data analysis. While
several avenues towards a statistical treatment of the diagrams have been explored
recently, we follow an alternative route that is motivated by the success of methods
based on the embedding of probability measures into reproducing kernel Hilbert
spaces. In fact, a positive definite kernel on persistence diagrams has recently
been proposed, connecting persistent homology to popular kernel-based learning
techniques such as support vector machines. However, important properties of that
kernel enabling a principled use in the context of probability measure embeddings
remain to be explored. Our contribution is to close this gap by proving universality
of a variant of the original kernel, and to demonstrate its effective use in twosample
hypothesis testing on synthetic as well as real-world data.
acknowledgement: This work was partially supported by the Austrian Science FUnd, project
no. KLI 00012.
alternative_title:
- Advances in Neural Information Processing Systems
author:
- first_name: Roland
full_name: Kwitt, Roland
last_name: Kwitt
- first_name: Stefan
full_name: Huber, Stefan
id: 4700A070-F248-11E8-B48F-1D18A9856A87
last_name: Huber
orcid: 0000-0002-8871-5814
- first_name: Marc
full_name: Niethammer, Marc
last_name: Niethammer
- first_name: Weili
full_name: Lin, Weili
last_name: Lin
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
citation:
ama: 'Kwitt R, Huber S, Niethammer M, Lin W, Bauer U. Statistical topological data
analysis-A kernel perspective. In: Vol 28. Neural Information Processing Systems;
2015:3070-3078.'
apa: 'Kwitt, R., Huber, S., Niethammer, M., Lin, W., & Bauer, U. (2015). Statistical
topological data analysis-A kernel perspective (Vol. 28, pp. 3070–3078). Presented
at the NIPS: Neural Information Processing Systems, Montreal, Canada: Neural Information
Processing Systems.'
chicago: Kwitt, Roland, Stefan Huber, Marc Niethammer, Weili Lin, and Ulrich Bauer.
“Statistical Topological Data Analysis-A Kernel Perspective,” 28:3070–78. Neural
Information Processing Systems, 2015.
ieee: 'R. Kwitt, S. Huber, M. Niethammer, W. Lin, and U. Bauer, “Statistical topological
data analysis-A kernel perspective,” presented at the NIPS: Neural Information
Processing Systems, Montreal, Canada, 2015, vol. 28, pp. 3070–3078.'
ista: 'Kwitt R, Huber S, Niethammer M, Lin W, Bauer U. 2015. Statistical topological
data analysis-A kernel perspective. NIPS: Neural Information Processing Systems,
Advances in Neural Information Processing Systems, vol. 28, 3070–3078.'
mla: Kwitt, Roland, et al. Statistical Topological Data Analysis-A Kernel Perspective.
Vol. 28, Neural Information Processing Systems, 2015, pp. 3070–78.
short: R. Kwitt, S. Huber, M. Niethammer, W. Lin, U. Bauer, in:, Neural Information
Processing Systems, 2015, pp. 3070–3078.
conference:
end_date: 2015-12-12
location: Montreal, Canada
name: 'NIPS: Neural Information Processing Systems'
start_date: 2015-12-07
date_created: 2018-12-11T11:51:56Z
date_published: 2015-12-01T00:00:00Z
date_updated: 2021-01-12T06:50:38Z
day: '01'
department:
- _id: HeEd
intvolume: ' 28'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://papers.nips.cc/paper/5887-statistical-topological-data-analysis-a-kernel-perspective
month: '12'
oa: 1
oa_version: Submitted Version
page: 3070 - 3078
publication_status: published
publisher: Neural Information Processing Systems
publist_id: '5782'
quality_controlled: '1'
status: public
title: Statistical topological data analysis-A kernel perspective
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 28
year: '2015'
...
---
_id: '1483'
abstract:
- lang: eng
text: Topological data analysis offers a rich source of valuable information to
study vision problems. Yet, so far we lack a theoretically sound connection to
popular kernel-based learning techniques, such as kernel SVMs or kernel PCA. In
this work, we establish such a connection by designing a multi-scale kernel for
persistence diagrams, a stable summary representation of topological features
in data. We show that this kernel is positive definite and prove its stability
with respect to the 1-Wasserstein distance. Experiments on two benchmark datasets
for 3D shape classification/retrieval and texture recognition show considerable
performance gains of the proposed method compared to an alternative approach that
is based on the recently introduced persistence landscapes.
author:
- first_name: Jan
full_name: Reininghaus, Jan
id: 4505473A-F248-11E8-B48F-1D18A9856A87
last_name: Reininghaus
- first_name: Stefan
full_name: Huber, Stefan
id: 4700A070-F248-11E8-B48F-1D18A9856A87
last_name: Huber
orcid: 0000-0002-8871-5814
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Roland
full_name: Kwitt, Roland
last_name: Kwitt
citation:
ama: 'Reininghaus J, Huber S, Bauer U, Kwitt R. A stable multi-scale kernel for
topological machine learning. In: IEEE; 2015:4741-4748. doi:10.1109/CVPR.2015.7299106'
apa: 'Reininghaus, J., Huber, S., Bauer, U., & Kwitt, R. (2015). A stable multi-scale
kernel for topological machine learning (pp. 4741–4748). Presented at the CVPR:
Computer Vision and Pattern Recognition, Boston, MA, USA: IEEE. https://doi.org/10.1109/CVPR.2015.7299106'
chicago: Reininghaus, Jan, Stefan Huber, Ulrich Bauer, and Roland Kwitt. “A Stable
Multi-Scale Kernel for Topological Machine Learning,” 4741–48. IEEE, 2015. https://doi.org/10.1109/CVPR.2015.7299106.
ieee: 'J. Reininghaus, S. Huber, U. Bauer, and R. Kwitt, “A stable multi-scale kernel
for topological machine learning,” presented at the CVPR: Computer Vision and
Pattern Recognition, Boston, MA, USA, 2015, pp. 4741–4748.'
ista: 'Reininghaus J, Huber S, Bauer U, Kwitt R. 2015. A stable multi-scale kernel
for topological machine learning. CVPR: Computer Vision and Pattern Recognition,
4741–4748.'
mla: Reininghaus, Jan, et al. A Stable Multi-Scale Kernel for Topological Machine
Learning. IEEE, 2015, pp. 4741–48, doi:10.1109/CVPR.2015.7299106.
short: J. Reininghaus, S. Huber, U. Bauer, R. Kwitt, in:, IEEE, 2015, pp. 4741–4748.
conference:
end_date: 2015-06-12
location: Boston, MA, USA
name: 'CVPR: Computer Vision and Pattern Recognition'
start_date: 2015-06-07
date_created: 2018-12-11T11:52:17Z
date_published: 2015-10-14T00:00:00Z
date_updated: 2021-01-12T06:51:03Z
day: '14'
department:
- _id: HeEd
doi: 10.1109/CVPR.2015.7299106
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1412.6821
month: '10'
oa: 1
oa_version: Preprint
page: 4741 - 4748
publication_identifier:
eisbn:
- '978-1-4673-6964-0 '
publication_status: published
publisher: IEEE
publist_id: '5709'
scopus_import: 1
status: public
title: A stable multi-scale kernel for topological machine learning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1805'
abstract:
- lang: eng
text: '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 double-struck R3. As a consequence, we show that it is NP-hard to simplify
level and sublevel sets of scalar functions on double-struck 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-hard.'
author:
- first_name: Dominique
full_name: Attali, Dominique
last_name: Attali
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Olivier
full_name: Devillers, Olivier
last_name: Devillers
- first_name: Marc
full_name: Glisse, Marc
last_name: Glisse
- first_name: André
full_name: Lieutier, André
last_name: Lieutier
citation:
ama: 'Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. Homological reconstruction
and simplification in R3. Computational Geometry: Theory and Applications.
2015;48(8):606-621. doi:10.1016/j.comgeo.2014.08.010'
apa: 'Attali, D., Bauer, U., Devillers, O., Glisse, M., & Lieutier, A. (2015).
Homological reconstruction and simplification in R3. Computational Geometry:
Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2014.08.010'
chicago: 'Attali, Dominique, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André
Lieutier. “Homological Reconstruction and Simplification in R3.” Computational
Geometry: Theory and Applications. Elsevier, 2015. https://doi.org/10.1016/j.comgeo.2014.08.010.'
ieee: 'D. Attali, U. Bauer, O. Devillers, M. Glisse, and A. Lieutier, “Homological
reconstruction and simplification in R3,” Computational Geometry: Theory and
Applications, vol. 48, no. 8. Elsevier, pp. 606–621, 2015.'
ista: 'Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. 2015. Homological reconstruction
and simplification in R3. Computational Geometry: Theory and Applications. 48(8),
606–621.'
mla: 'Attali, Dominique, et al. “Homological Reconstruction and Simplification in
R3.” Computational Geometry: Theory and Applications, vol. 48, no. 8, Elsevier,
2015, pp. 606–21, doi:10.1016/j.comgeo.2014.08.010.'
short: 'D. Attali, U. Bauer, O. Devillers, M. Glisse, A. Lieutier, Computational
Geometry: Theory and Applications 48 (2015) 606–621.'
date_created: 2018-12-11T11:54:06Z
date_published: 2015-06-03T00:00:00Z
date_updated: 2023-02-23T10:59:19Z
day: '03'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2014.08.010
ec_funded: 1
intvolume: ' 48'
issue: '8'
language:
- iso: eng
month: '06'
oa_version: None
page: 606 - 621
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: 'Computational Geometry: Theory and Applications'
publication_status: published
publisher: Elsevier
publist_id: '5305'
quality_controlled: '1'
related_material:
record:
- id: '2812'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Homological reconstruction and simplification in R3
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 48
year: '2015'
...
---
_id: '2043'
abstract:
- lang: eng
text: Persistent homology is a popular and powerful tool for capturing topological
features of data. Advances in algorithms for computing persistent homology have
reduced the computation time drastically – as long as the algorithm does not exhaust
the available memory. Following up on a recently presented parallel method for
persistence computation on shared memory systems [1], we demonstrate that a simple
adaption of the standard reduction algorithm leads to a variant for distributed
systems. Our algorithmic design ensures that the data is distributed over the
nodes without redundancy; this permits the computation of much larger instances
than on a single machine. Moreover, we observe that the parallelism at least compensates
for the overhead caused by communication between nodes, and often even speeds
up the computation compared to sequential and even parallel shared memory algorithms.
In our experiments, we were able to compute the persistent homology of filtrations
with more than a billion (109) elements within seconds on a cluster with 32 nodes
using less than 6GB of memory per node.
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Michael
full_name: Kerber, Michael
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Jan
full_name: Reininghaus, Jan
id: 4505473A-F248-11E8-B48F-1D18A9856A87
last_name: Reininghaus
citation:
ama: 'Bauer U, Kerber M, Reininghaus J. Distributed computation of persistent homology.
In: McGeoch C, Meyer U, eds. Proceedings of the Workshop on Algorithm Engineering
and Experiments. Society of Industrial and Applied Mathematics; 2014:31-38.
doi:10.1137/1.9781611973198.4'
apa: 'Bauer, U., Kerber, M., & Reininghaus, J. (2014). Distributed computation
of persistent homology. In C. McGeoch & U. Meyer (Eds.), Proceedings of
the Workshop on Algorithm Engineering and Experiments (pp. 31–38). Portland,
USA: Society of Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973198.4'
chicago: Bauer, Ulrich, Michael Kerber, and Jan Reininghaus. “Distributed Computation
of Persistent Homology.” In Proceedings of the Workshop on Algorithm Engineering
and Experiments, edited by Catherine McGeoch and Ulrich Meyer, 31–38. Society
of Industrial and Applied Mathematics, 2014. https://doi.org/10.1137/1.9781611973198.4.
ieee: U. Bauer, M. Kerber, and J. Reininghaus, “Distributed computation of persistent
homology,” in Proceedings of the Workshop on Algorithm Engineering and Experiments,
Portland, USA, 2014, pp. 31–38.
ista: 'Bauer U, Kerber M, Reininghaus J. 2014. Distributed computation of persistent
homology. Proceedings of the Workshop on Algorithm Engineering and Experiments.
ALENEX: Algorithm Engineering and Experiments, 31–38.'
mla: Bauer, Ulrich, et al. “Distributed Computation of Persistent Homology.” Proceedings
of the Workshop on Algorithm Engineering and Experiments, edited by Catherine McGeoch
and Ulrich Meyer, Society of Industrial and Applied Mathematics, 2014, pp. 31–38,
doi:10.1137/1.9781611973198.4.
short: U. Bauer, M. Kerber, J. Reininghaus, in:, C. McGeoch, U. Meyer (Eds.), Proceedings
of the Workshop on Algorithm Engineering and Experiments, Society of Industrial
and Applied Mathematics, 2014, pp. 31–38.
conference:
end_date: 2014-01-05
location: Portland, USA
name: 'ALENEX: Algorithm Engineering and Experiments'
start_date: 2014-01-05
date_created: 2018-12-11T11:55:23Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:54:56Z
day: '01'
department:
- _id: HeEd
doi: 10.1137/1.9781611973198.4
ec_funded: 1
editor:
- first_name: Catherine
full_name: ' McGeoch, Catherine'
last_name: ' McGeoch'
- first_name: Ulrich
full_name: Meyer, Ulrich
last_name: Meyer
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1310.0710
month: '01'
oa: 1
oa_version: Submitted Version
page: 31 - 38
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Proceedings of the Workshop on Algorithm Engineering and Experiments
publication_status: published
publisher: Society of Industrial and Applied Mathematics
publist_id: '5008'
quality_controlled: '1'
scopus_import: 1
status: public
title: Distributed computation of persistent homology
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2044'
abstract:
- lang: eng
text: We present a parallel algorithm for computing the persistent homology of a
filtered chain complex. Our approach differs from the commonly used reduction
algorithm by first computing persistence pairs within local chunks, then simplifying
the unpaired columns, and finally applying standard reduction on the simplified
matrix. The approach generalizes a technique by Günther et al., which uses discrete
Morse Theory to compute persistence; we derive the same worst-case complexity
bound in a more general context. The algorithm employs several practical optimization
techniques, which are of independent interest. Our sequential implementation of
the algorithm is competitive with state-of-the-art methods, and we further improve
the performance through parallel computation.
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Michael
full_name: Kerber, Michael
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Jan
full_name: Reininghaus, Jan
id: 4505473A-F248-11E8-B48F-1D18A9856A87
last_name: Reininghaus
citation:
ama: 'Bauer U, Kerber M, Reininghaus J. Clear and Compress: Computing Persistent
Homology in Chunks. In: Bremer P-T, Hotz I, Pascucci V, Peikert R, eds. Topological
Methods in Data Analysis and Visualization III. Mathematics and Visualization.
Springer; 2014:103-117. doi:10.1007/978-3-319-04099-8_7'
apa: 'Bauer, U., Kerber, M., & Reininghaus, J. (2014). Clear and Compress: Computing
Persistent Homology in Chunks. In P.-T. Bremer, I. Hotz, V. Pascucci, & R.
Peikert (Eds.), Topological Methods in Data Analysis and Visualization III
(pp. 103–117). Springer. https://doi.org/10.1007/978-3-319-04099-8_7'
chicago: 'Bauer, Ulrich, Michael Kerber, and Jan Reininghaus. “Clear and Compress:
Computing Persistent Homology in Chunks.” In Topological Methods in Data Analysis
and Visualization III, edited by Peer-Timo Bremer, Ingrid Hotz, Valerio Pascucci,
and Ronald Peikert, 103–17. Mathematics and Visualization. Springer, 2014. https://doi.org/10.1007/978-3-319-04099-8_7.'
ieee: 'U. Bauer, M. Kerber, and J. Reininghaus, “Clear and Compress: Computing Persistent
Homology in Chunks,” in Topological Methods in Data Analysis and Visualization
III, P.-T. Bremer, I. Hotz, V. Pascucci, and R. Peikert, Eds. Springer, 2014,
pp. 103–117.'
ista: 'Bauer U, Kerber M, Reininghaus J. 2014.Clear and Compress: Computing Persistent
Homology in Chunks. In: Topological Methods in Data Analysis and Visualization
III. , 103–117.'
mla: 'Bauer, Ulrich, et al. “Clear and Compress: Computing Persistent Homology in
Chunks.” Topological Methods in Data Analysis and Visualization III, edited
by Peer-Timo Bremer et al., Springer, 2014, pp. 103–17, doi:10.1007/978-3-319-04099-8_7.'
short: U. Bauer, M. Kerber, J. Reininghaus, in:, P.-T. Bremer, I. Hotz, V. Pascucci,
R. Peikert (Eds.), Topological Methods in Data Analysis and Visualization III,
Springer, 2014, pp. 103–117.
date_created: 2018-12-11T11:55:23Z
date_published: 2014-03-19T00:00:00Z
date_updated: 2021-01-12T06:54:56Z
day: '19'
department:
- _id: HeEd
doi: 10.1007/978-3-319-04099-8_7
ec_funded: 1
editor:
- first_name: Peer-Timo
full_name: Bremer, Peer-Timo
last_name: Bremer
- first_name: Ingrid
full_name: Hotz, Ingrid
last_name: Hotz
- first_name: Valerio
full_name: Pascucci, Valerio
last_name: Pascucci
- first_name: Ronald
full_name: Peikert, Ronald
last_name: Peikert
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1303.0477
month: '03'
oa: 1
oa_version: Submitted Version
page: 103 - 117
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Topological Methods in Data Analysis and Visualization III
publication_status: published
publisher: Springer
publist_id: '5007'
quality_controlled: '1'
scopus_import: 1
series_title: Mathematics and Visualization
status: public
title: 'Clear and Compress: Computing Persistent Homology in Chunks'
type: book_chapter
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2153'
abstract:
- lang: eng
text: 'We define a simple, explicit map sending a morphism f : M → N of pointwise
finite dimensional persistence modules to a matching between the barcodes of M
and N. Our main result is that, in a precise sense, the quality of this matching
is tightly controlled by the lengths of the longest intervals in the barcodes
of ker f and coker f . As an immediate corollary, we obtain a new proof of the
algebraic stability theorem for persistence barcodes [5, 9], a fundamental result
in the theory of persistent homology. In contrast to previous proofs, ours shows
explicitly how a δ-interleaving morphism between two persistence modules induces
a δ-matching between the barcodes of the two modules. Our main result also specializes
to a structure theorem for submodules and quotients of persistence modules. Copyright
is held by the owner/author(s).'
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Michael
full_name: Lesnick, Michael
last_name: Lesnick
citation:
ama: 'Bauer U, Lesnick M. Induced matchings of barcodes and the algebraic stability
of persistence. In: Proceedings of the Annual Symposium on Computational Geometry.
ACM; 2014:355-364. doi:10.1145/2582112.2582168'
apa: 'Bauer, U., & Lesnick, M. (2014). Induced matchings of barcodes and the
algebraic stability of persistence. In Proceedings of the Annual Symposium
on Computational Geometry (pp. 355–364). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582168'
chicago: Bauer, Ulrich, and Michael Lesnick. “Induced Matchings of Barcodes and
the Algebraic Stability of Persistence.” In Proceedings of the Annual Symposium
on Computational Geometry, 355–64. ACM, 2014. https://doi.org/10.1145/2582112.2582168.
ieee: U. Bauer and M. Lesnick, “Induced matchings of barcodes and the algebraic
stability of persistence,” in Proceedings of the Annual Symposium on Computational
Geometry, Kyoto, Japan, 2014, pp. 355–364.
ista: 'Bauer U, Lesnick M. 2014. Induced matchings of barcodes and the algebraic
stability of persistence. Proceedings of the Annual Symposium on Computational
Geometry. SoCG: Symposium on Computational Geometry, 355–364.'
mla: Bauer, Ulrich, and Michael Lesnick. “Induced Matchings of Barcodes and the
Algebraic Stability of Persistence.” Proceedings of the Annual Symposium on
Computational Geometry, ACM, 2014, pp. 355–64, doi:10.1145/2582112.2582168.
short: U. Bauer, M. Lesnick, in:, Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 355–364.
conference:
end_date: 2014-06-11
location: Kyoto, Japan
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2014-06-08
date_created: 2018-12-11T11:56:01Z
date_published: 2014-06-01T00:00:00Z
date_updated: 2021-01-12T06:55:38Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/2582112.2582168
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1311.3681
month: '06'
oa: 1
oa_version: Submitted Version
page: 355 - 364
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4853'
quality_controlled: '1'
scopus_import: 1
status: public
title: Induced matchings of barcodes and the algebraic stability of persistence
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2156'
abstract:
- lang: eng
text: We propose a metric for Reeb graphs, called the functional distortion distance.
Under this distance, the Reeb graph is stable against small changes of input functions.
At the same time, it remains discriminative at differentiating input functions.
In particular, the main result is that the functional distortion distance between
two Reeb graphs is bounded from below by the bottleneck distance between both
the ordinary and extended persistence diagrams for appropriate dimensions. As
an application of our results, we analyze a natural simplification scheme for
Reeb graphs, and show that persistent features in Reeb graph remains persistent
under simplification. Understanding the stability of important features of the
Reeb graph under simplification is an interesting problem on its own right, and
critical to the practical usage of Reeb graphs. Copyright is held by the owner/author(s).
acknowledgement: National Science Foundation under grants CCF-1319406, CCF-1116258.
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Xiaoyin
full_name: Ge, Xiaoyin
last_name: Ge
- first_name: Yusu
full_name: Wang, Yusu
last_name: Wang
citation:
ama: 'Bauer U, Ge X, Wang Y. Measuring distance between Reeb graphs. In: Proceedings
of the Annual Symposium on Computational Geometry. ACM; 2014:464-473. doi:10.1145/2582112.2582169'
apa: 'Bauer, U., Ge, X., & Wang, Y. (2014). Measuring distance between Reeb
graphs. In Proceedings of the Annual Symposium on Computational Geometry
(pp. 464–473). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582169'
chicago: Bauer, Ulrich, Xiaoyin Ge, and Yusu Wang. “Measuring Distance between Reeb
Graphs.” In Proceedings of the Annual Symposium on Computational Geometry,
464–73. ACM, 2014. https://doi.org/10.1145/2582112.2582169.
ieee: U. Bauer, X. Ge, and Y. Wang, “Measuring distance between Reeb graphs,” in
Proceedings of the Annual Symposium on Computational Geometry, Kyoto, Japan,
2014, pp. 464–473.
ista: 'Bauer U, Ge X, Wang Y. 2014. Measuring distance between Reeb graphs. Proceedings
of the Annual Symposium on Computational Geometry. SoCG: Symposium on Computational
Geometry, 464–473.'
mla: Bauer, Ulrich, et al. “Measuring Distance between Reeb Graphs.” Proceedings
of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 464–73,
doi:10.1145/2582112.2582169.
short: U. Bauer, X. Ge, Y. Wang, in:, Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 464–473.
conference:
end_date: 2014-06-11
location: Kyoto, Japan
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2014-06-08
date_created: 2018-12-11T11:56:02Z
date_published: 2014-06-01T00:00:00Z
date_updated: 2021-01-12T06:55:39Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/2582112.2582169
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1307.2839
month: '06'
oa: 1
oa_version: Submitted Version
page: 464 - 473
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4850'
quality_controlled: '1'
scopus_import: 1
status: public
title: Measuring distance between Reeb graphs
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2155'
abstract:
- lang: eng
text: Given a finite set of points in Rn and a positive radius, we study the Čech,
Delaunay-Čech, alpha, and wrap complexes as instances of a generalized discrete
Morse theory. We prove that the latter three complexes are simple-homotopy equivalent.
Our results have applications in topological data analysis and in the reconstruction
of shapes from sampled data. Copyright is held by the owner/author(s).
acknowledgement: This research is partially supported by ESF under the ACAT Research
Network Programme, and by the Russian Government under mega project 11.G34.31.0053
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Bauer U, Edelsbrunner H. The morse theory of Čech and Delaunay filtrations.
In: Proceedings of the Annual Symposium on Computational Geometry. ACM;
2014:484-490. doi:10.1145/2582112.2582167'
apa: 'Bauer, U., & Edelsbrunner, H. (2014). The morse theory of Čech and Delaunay
filtrations. In Proceedings of the Annual Symposium on Computational Geometry
(pp. 484–490). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582167'
chicago: Bauer, Ulrich, and Herbert Edelsbrunner. “The Morse Theory of Čech and
Delaunay Filtrations.” In Proceedings of the Annual Symposium on Computational
Geometry, 484–90. ACM, 2014. https://doi.org/10.1145/2582112.2582167.
ieee: U. Bauer and H. Edelsbrunner, “The morse theory of Čech and Delaunay filtrations,”
in Proceedings of the Annual Symposium on Computational Geometry, Kyoto,
Japan, 2014, pp. 484–490.
ista: 'Bauer U, Edelsbrunner H. 2014. The morse theory of Čech and Delaunay filtrations.
Proceedings of the Annual Symposium on Computational Geometry. SoCG: Symposium
on Computational Geometry, 484–490.'
mla: Bauer, Ulrich, and Herbert Edelsbrunner. “The Morse Theory of Čech and Delaunay
Filtrations.” Proceedings of the Annual Symposium on Computational Geometry,
ACM, 2014, pp. 484–90, doi:10.1145/2582112.2582167.
short: U. Bauer, H. Edelsbrunner, in:, Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 484–490.
conference:
end_date: 2014-06-11
location: Kyoto, Japan
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2014-06-08
date_created: 2018-12-11T11:56:01Z
date_published: 2014-06-01T00:00:00Z
date_updated: 2021-01-12T06:55:38Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/2582112.2582167
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1312.1231
month: '06'
oa: 1
oa_version: Submitted Version
page: 484 - 490
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4851'
quality_controlled: '1'
scopus_import: 1
status: public
title: The morse theory of Čech and Delaunay filtrations
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '10894'
abstract:
- lang: eng
text: PHAT is a C++ library for the computation of persistent homology by matrix
reduction. We aim for a simple generic design that decouples algorithms from data
structures without sacrificing efficiency or user-friendliness. This makes PHAT
a versatile platform for experimenting with algorithmic ideas and comparing them
to state of the art implementations.
article_processing_charge: No
author:
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Michael
full_name: Kerber, Michael
last_name: Kerber
- first_name: Jan
full_name: Reininghaus, Jan
id: 4505473A-F248-11E8-B48F-1D18A9856A87
last_name: Reininghaus
- first_name: Hubert
full_name: Wagner, Hubert
last_name: Wagner
citation:
ama: 'Bauer U, Kerber M, Reininghaus J, Wagner H. PHAT – Persistent Homology Algorithms
Toolbox. In: ICMS 2014: International Congress on Mathematical Software.
Vol 8592. LNCS. Berlin, Heidelberg: Springer Berlin Heidelberg; 2014:137-143.
doi:10.1007/978-3-662-44199-2_24'
apa: 'Bauer, U., Kerber, M., Reininghaus, J., & Wagner, H. (2014). PHAT – Persistent
Homology Algorithms Toolbox. In ICMS 2014: International Congress on Mathematical
Software (Vol. 8592, pp. 137–143). Berlin, Heidelberg: Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-662-44199-2_24'
chicago: 'Bauer, Ulrich, Michael Kerber, Jan Reininghaus, and Hubert Wagner. “PHAT
– Persistent Homology Algorithms Toolbox.” In ICMS 2014: International Congress
on Mathematical Software, 8592:137–43. LNCS. Berlin, Heidelberg: Springer
Berlin Heidelberg, 2014. https://doi.org/10.1007/978-3-662-44199-2_24.'
ieee: 'U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner, “PHAT – Persistent Homology
Algorithms Toolbox,” in ICMS 2014: International Congress on Mathematical Software,
Seoul, South Korea, 2014, vol. 8592, pp. 137–143.'
ista: 'Bauer U, Kerber M, Reininghaus J, Wagner H. 2014. PHAT – Persistent Homology
Algorithms Toolbox. ICMS 2014: International Congress on Mathematical Software.
ICMS: International Congress on Mathematical SoftwareLNCS vol. 8592, 137–143.'
mla: 'Bauer, Ulrich, et al. “PHAT – Persistent Homology Algorithms Toolbox.” ICMS
2014: International Congress on Mathematical Software, vol. 8592, Springer
Berlin Heidelberg, 2014, pp. 137–43, doi:10.1007/978-3-662-44199-2_24.'
short: 'U. Bauer, M. Kerber, J. Reininghaus, H. Wagner, in:, ICMS 2014: International
Congress on Mathematical Software, Springer Berlin Heidelberg, Berlin, Heidelberg,
2014, pp. 137–143.'
conference:
end_date: 2014-08-09
location: Seoul, South Korea
name: 'ICMS: International Congress on Mathematical Software'
start_date: 2014-08-05
date_created: 2022-03-21T07:12:16Z
date_published: 2014-09-01T00:00:00Z
date_updated: 2023-09-20T09:42:40Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-662-44199-2_24
intvolume: ' 8592'
language:
- iso: eng
month: '09'
oa_version: None
page: 137-143
place: Berlin, Heidelberg
publication: 'ICMS 2014: International Congress on Mathematical Software'
publication_identifier:
eisbn:
- '9783662441992'
eissn:
- 1611-3349
isbn:
- '9783662441985'
issn:
- 0302-9743
publication_status: published
publisher: Springer Berlin Heidelberg
quality_controlled: '1'
related_material:
record:
- id: '1433'
relation: later_version
status: public
scopus_import: '1'
series_title: LNCS
status: public
title: PHAT – Persistent Homology Algorithms Toolbox
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 8592
year: '2014'
...
---
_id: '2812'
abstract:
- lang: eng
text: '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 ℝ3. 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-hard.'
acknowledgement: Some of the authors were partially supported by the GIGA ANR grant
(contract ANR-09-BLAN-0331-01) and the European project CG-Learning (contract 255827).
author:
- first_name: Dominique
full_name: Attali, Dominique
last_name: Attali
- first_name: Ulrich
full_name: Bauer, Ulrich
id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
last_name: Bauer
orcid: 0000-0002-9683-0724
- first_name: Olivier
full_name: Devillers, Olivier
last_name: Devillers
- first_name: Marc
full_name: Glisse, Marc
last_name: Glisse
- first_name: André
full_name: Lieutier, André
last_name: Lieutier
citation:
ama: 'Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. Homological reconstruction
and simplification in R3. In: Proceedings of the 29th Annual Symposium on Computational
Geometry. ACM; 2013:117-125. doi:10.1145/2462356.2462373'
apa: 'Attali, D., Bauer, U., Devillers, O., Glisse, M., & Lieutier, A. (2013).
Homological reconstruction and simplification in R3. In Proceedings of the
29th annual symposium on Computational Geometry (pp. 117–125). Rio de Janeiro,
Brazil: ACM. https://doi.org/10.1145/2462356.2462373'
chicago: Attali, Dominique, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André
Lieutier. “Homological Reconstruction and Simplification in R3.” In Proceedings
of the 29th Annual Symposium on Computational Geometry, 117–25. ACM, 2013.
https://doi.org/10.1145/2462356.2462373.
ieee: D. Attali, U. Bauer, O. Devillers, M. Glisse, and A. Lieutier, “Homological
reconstruction and simplification in R3,” in Proceedings of the 29th annual
symposium on Computational Geometry, Rio de Janeiro, Brazil, 2013, pp. 117–125.
ista: 'Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. 2013. Homological reconstruction
and simplification in R3. Proceedings of the 29th annual symposium on Computational
Geometry. SoCG: Symposium on Computational Geometry, 117–125.'
mla: Attali, Dominique, et al. “Homological Reconstruction and Simplification in
R3.” Proceedings of the 29th Annual Symposium on Computational Geometry,
ACM, 2013, pp. 117–25, doi:10.1145/2462356.2462373.
short: D. Attali, U. Bauer, O. Devillers, M. Glisse, A. Lieutier, in:, Proceedings
of the 29th Annual Symposium on Computational Geometry, ACM, 2013, pp. 117–125.
conference:
end_date: 2013-06-20
location: Rio de Janeiro, Brazil
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2013-06-17
date_created: 2018-12-11T11:59:44Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2023-02-23T10:15:15Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/2462356.2462373
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://hal.archives-ouvertes.fr/hal-00833791/
month: '06'
oa: 1
oa_version: Submitted Version
page: 117 - 125
publication: Proceedings of the 29th annual symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4072'
quality_controlled: '1'
related_material:
record:
- id: '1805'
relation: later_version
status: public
scopus_import: 1
status: public
title: Homological reconstruction and simplification in R3
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...