---
_id: '12709'
abstract:
- lang: eng
text: Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within
distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter
family of spaces that grow larger when r increases or k decreases, called the
multicover bifiltration. Motivated by the problem of computing the homology of
this bifiltration, we introduce two closely related combinatorial bifiltrations,
one polyhedral and the other simplicial, which are both topologically equivalent
to the multicover bifiltration and far smaller than a Čech-based model considered
in prior work of Sheehy. Our polyhedral construction is a bifiltration of the
rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using
a variant of an algorithm given by these authors as well. Using an implementation
for dimension 2 and 3, we provide experimental results. Our simplicial construction
is useful for understanding the polyhedral construction and proving its correctness.
acknowledgement: We thank the anonymous reviewers for many helpful comments and suggestions,
which led to substantial improvements of the paper. The first two authors were supported
by the Austrian Science Fund (FWF) grant number P 29984-N35 and W1230. The first
author was partly supported by an Austrian Marshall Plan Scholarship, and by the
Brummer & Partners MathDataLab. A conference version of this paper was presented
at the 37th International Symposium on Computational Geometry (SoCG 2021). Open
access funding provided by the Royal Institute of Technology.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: René
full_name: Corbet, René
last_name: Corbet
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Lesnick, Michael
last_name: Lesnick
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
citation:
ama: Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration.
Discrete and Computational Geometry. 2023;70:376-405. doi:10.1007/s00454-022-00476-8
apa: Corbet, R., Kerber, M., Lesnick, M., & Osang, G. F. (2023). Computing the
multicover bifiltration. Discrete and Computational Geometry. Springer
Nature. https://doi.org/10.1007/s00454-022-00476-8
chicago: Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing
the Multicover Bifiltration.” Discrete and Computational Geometry. Springer
Nature, 2023. https://doi.org/10.1007/s00454-022-00476-8.
ieee: R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover
bifiltration,” Discrete and Computational Geometry, vol. 70. Springer Nature,
pp. 376–405, 2023.
ista: Corbet R, Kerber M, Lesnick M, Osang GF. 2023. Computing the multicover bifiltration.
Discrete and Computational Geometry. 70, 376–405.
mla: Corbet, René, et al. “Computing the Multicover Bifiltration.” Discrete and
Computational Geometry, vol. 70, Springer Nature, 2023, pp. 376–405, doi:10.1007/s00454-022-00476-8.
short: R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, Discrete and Computational
Geometry 70 (2023) 376–405.
date_created: 2023-03-05T23:01:06Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2023-10-04T12:03:40Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/s00454-022-00476-8
external_id:
arxiv:
- '2103.07823'
isi:
- '000936496800001'
file:
- access_level: open_access
checksum: 71ce7e59f7ee4620acc704fecca620c2
content_type: application/pdf
creator: cchlebak
date_created: 2023-03-07T14:40:14Z
date_updated: 2023-03-07T14:40:14Z
file_id: '12715'
file_name: 2023_DisCompGeo_Corbet.pdf
file_size: 1359323
relation: main_file
success: 1
file_date_updated: 2023-03-07T14:40:14Z
has_accepted_license: '1'
intvolume: ' 70'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 376-405
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '9605'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Computing the multicover bifiltration
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 70
year: '2023'
...
---
_id: '2906'
abstract:
- lang: eng
text: "Motivated by an application in cell biology, we describe an extension of
the kinetic data structures framework from Delaunay triangulations to fixed-radius
alpha complexes. Our algorithm is implemented\r\nusing CGAL, following the exact
geometric computation paradigm. We report on several\r\ntechniques to accelerate
the computation that turn our implementation applicable to the underlying biological\r\nproblem."
alternative_title:
- ALENEX
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Kerber M, Edelsbrunner H. 3D kinetic alpha complexes and their implementation.
In: 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments.
Society of Industrial and Applied Mathematics; 2013:70-77. doi:10.1137/1.9781611972931.6'
apa: 'Kerber, M., & Edelsbrunner, H. (2013). 3D kinetic alpha complexes and
their implementation. In 2013 Proceedings of the 15th Workshop on Algorithm
Engineering and Experiments (pp. 70–77). New Orleans, LA, United States: Society
of Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611972931.6'
chicago: Kerber, Michael, and Herbert Edelsbrunner. “3D Kinetic Alpha Complexes
and Their Implementation.” In 2013 Proceedings of the 15th Workshop on Algorithm
Engineering and Experiments, 70–77. Society of Industrial and Applied Mathematics,
2013. https://doi.org/10.1137/1.9781611972931.6.
ieee: M. Kerber and H. Edelsbrunner, “3D kinetic alpha complexes and their implementation,”
in 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments,
New Orleans, LA, United States, 2013, pp. 70–77.
ista: 'Kerber M, Edelsbrunner H. 2013. 3D kinetic alpha complexes and their implementation.
2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments.
ALENEX: Algorithm Engineering and Experiments, ALENEX, , 70–77.'
mla: Kerber, Michael, and Herbert Edelsbrunner. “3D Kinetic Alpha Complexes and
Their Implementation.” 2013 Proceedings of the 15th Workshop on Algorithm Engineering
and Experiments, Society of Industrial and Applied Mathematics, 2013, pp.
70–77, doi:10.1137/1.9781611972931.6.
short: M. Kerber, H. Edelsbrunner, in:, 2013 Proceedings of the 15th Workshop on
Algorithm Engineering and Experiments, Society of Industrial and Applied Mathematics,
2013, pp. 70–77.
conference:
end_date: 2013-01-07
location: New Orleans, LA, United States
name: 'ALENEX: Algorithm Engineering and Experiments'
start_date: 2013-01-07
date_created: 2018-12-11T12:00:16Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T07:00:36Z
day: '01'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.1137/1.9781611972931.6
file:
- access_level: open_access
checksum: a15a3ba22df9445731507f3e06c9fcee
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:57Z
date_updated: 2020-07-14T12:45:52Z
file_id: '4720'
file_name: IST-2016-547-v1+1_2013-P-08-MedusaII.pdf
file_size: 403013
relation: main_file
file_date_updated: 2020-07-14T12:45:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 70 - 77
publication: 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments
publication_status: published
publisher: Society of Industrial and Applied Mathematics
publist_id: '3841'
pubrep_id: '547'
quality_controlled: '1'
scopus_import: 1
status: public
title: 3D kinetic alpha complexes and their implementation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2939'
abstract:
- lang: eng
text: In this paper, we present the first output-sensitive algorithm to compute
the persistence diagram of a filtered simplicial complex. For any Γ > 0, it
returns only those homology classes with persistence at least Γ. Instead of the
classical reduction via column operations, our algorithm performs rank computations
on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0, 1), the
running time is O (C (1 - δ) Γ R d (n) log n), where C (1 - δ) Γ is the number
of homology classes with persistence at least (1 - δ) Γ, n is the total number
of simplices in the complex, d its dimension, and R d (n) is the complexity of
computing the rank of an n × n matrix with O (d n) nonzero entries. Depending
on the choice of the rank algorithm, this yields a deterministic O (C (1 - δ)
Γ n 2.376) algorithm, an O (C (1 - δ) Γ n 2.28) Las-Vegas algorithm, or an O (C
(1 - δ) Γ n 2 + ε{lunate}) Monte-Carlo algorithm for an arbitrary ε{lunate} >
0. The space complexity of the Monte-Carlo version is bounded by O (d n) = O (n
log n).
acknowledgement: The authors thank Herbert Edelsbrunner for many helpful discussions
and suggestions. Moreover, they are grateful for the careful reviews that helped
to improve the quality of the paper.
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Chen C, Kerber M. An output sensitive algorithm for persistent homology. Computational
Geometry: Theory and Applications. 2013;46(4):435-447. doi:10.1016/j.comgeo.2012.02.010'
apa: 'Chen, C., & Kerber, M. (2013). An output sensitive algorithm for persistent
homology. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2012.02.010'
chicago: 'Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent
Homology.” Computational Geometry: Theory and Applications. Elsevier, 2013.
https://doi.org/10.1016/j.comgeo.2012.02.010.'
ieee: 'C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,”
Computational Geometry: Theory and Applications, vol. 46, no. 4. Elsevier,
pp. 435–447, 2013.'
ista: 'Chen C, Kerber M. 2013. An output sensitive algorithm for persistent homology.
Computational Geometry: Theory and Applications. 46(4), 435–447.'
mla: 'Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent
Homology.” Computational Geometry: Theory and Applications, vol. 46, no.
4, Elsevier, 2013, pp. 435–47, doi:10.1016/j.comgeo.2012.02.010.'
short: 'C. Chen, M. Kerber, Computational Geometry: Theory and Applications 46 (2013)
435–447.'
date_created: 2018-12-11T12:00:27Z
date_published: 2013-05-01T00:00:00Z
date_updated: 2023-02-23T11:24:10Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2012.02.010
intvolume: ' 46'
issue: '4'
language:
- iso: eng
month: '05'
oa_version: None
page: 435 - 447
publication: 'Computational Geometry: Theory and Applications'
publication_status: published
publisher: Elsevier
publist_id: '3796'
quality_controlled: '1'
related_material:
record:
- id: '3367'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: An output sensitive algorithm for persistent homology
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 46
year: '2013'
...
---
_id: '3115'
abstract:
- lang: eng
text: 'We consider the offset-deconstruction problem: Given a polygonal shape Q
with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance,
as the Minkowski sum of another polygonal shape P with a disk of fixed radius?
If it does, we also seek a preferably simple-looking solution P; then, P''s offset
constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We
give an O(nlogn)-time exact decision algorithm that handles any polygonal shape,
assuming the real-RAM model of computation. A variant of the algorithm, which
we have implemented using the cgal library, is based on rational arithmetic and
answers the same deconstruction problem up to an uncertainty parameter δ its running
time additionally depends on δ. If the input shape is found to be approximable,
this algorithm also computes an approximate solution for the problem. It also
allows us to solve parameter-optimization problems induced by the offset-deconstruction
problem. For convex shapes, the complexity of the exact decision algorithm drops
to O(n), which is also the time required to compute a solution P with at most
one more vertex than a vertex-minimal one.'
acknowledgement: "We thank Eyal Flato (Plataine Ltd.) for raising the offset-deconstruction
problem in connection with wood cutting. We also thank Tim Bretl (UIUC) for suggesting
the digital-pen offset-deconstruction problem. This work has been supported in part
by the Israel Science Foundation (grant no. 1102/11), by the German–Israeli Foundation
(grant no. 969/07), by the Hermann Minkowski–Minerva Center for Geometry at Tel
Aviv University, and by the EU Project under Contract No. 255827 (CGL—Computational
Geometry Learning).\r\n"
arxiv: 1
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Dan
full_name: Halperin, Dan
last_name: Halperin
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Roza
full_name: Pogalnikova, Roza
last_name: Pogalnikova
citation:
ama: Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate
offsets. Discrete & Computational Geometry. 2012;48(4):964-989. doi:10.1007/s00454-012-9441-5
apa: Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2012). Deconstructing
approximate offsets. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-012-9441-5
chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing
Approximate Offsets.” Discrete & Computational Geometry. Springer,
2012. https://doi.org/10.1007/s00454-012-9441-5.
ieee: E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing
approximate offsets,” Discrete & Computational Geometry, vol. 48, no.
4. Springer, pp. 964–989, 2012.
ista: Berberich E, Halperin D, Kerber M, Pogalnikova R. 2012. Deconstructing approximate
offsets. Discrete & Computational Geometry. 48(4), 964–989.
mla: Berberich, Eric, et al. “Deconstructing Approximate Offsets.” Discrete &
Computational Geometry, vol. 48, no. 4, Springer, 2012, pp. 964–89, doi:10.1007/s00454-012-9441-5.
short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, Discrete & Computational
Geometry 48 (2012) 964–989.
date_created: 2018-12-11T12:01:28Z
date_published: 2012-12-01T00:00:00Z
date_updated: 2023-02-23T11:22:30Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s00454-012-9441-5
external_id:
arxiv:
- '1109.2158'
intvolume: ' 48'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1109.2158
month: '12'
oa: 1
oa_version: Preprint
page: 964 - 989
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '3584'
quality_controlled: '1'
related_material:
record:
- id: '3329'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Deconstructing approximate offsets
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 48
year: '2012'
...
---
_id: '3120'
abstract:
- lang: eng
text: We introduce a strategy based on Kustin-Miller unprojection that allows us
to construct many hundreds of Gorenstein codimension 4 ideals with 9 × 16 resolutions
(that is, nine equations and sixteen first syzygies). Our two basic games are
called Tom and Jerry; the main application is the biregular construction of most
of the anticanonically polarised Mori Fano 3-folds of Altinok's thesis. There
are 115 cases whose numerical data (in effect, the Hilbert series) allow a Type
I projection. In every case, at least one Tom and one Jerry construction works,
providing at least two deformation families of quasismooth Fano 3-folds having
the same numerics but different topology. © 2012 Copyright Foundation Compositio
Mathematica.
acknowledgement: This research is supported by the Korean Government WCU Grant R33-2008-000-10101-0.
author:
- first_name: Gavin
full_name: Brown, Gavin
last_name: Brown
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Miles
full_name: Reid, Miles
last_name: Reid
citation:
ama: Brown G, Kerber M, Reid M. Fano 3 folds in codimension 4 Tom and Jerry Part
I. Compositio Mathematica. 2012;148(4):1171-1194. doi:10.1112/S0010437X11007226
apa: Brown, G., Kerber, M., & Reid, M. (2012). Fano 3 folds in codimension 4
Tom and Jerry Part I. Compositio Mathematica. Cambridge University Press.
https://doi.org/10.1112/S0010437X11007226
chicago: Brown, Gavin, Michael Kerber, and Miles Reid. “Fano 3 Folds in Codimension
4 Tom and Jerry Part I.” Compositio Mathematica. Cambridge University Press,
2012. https://doi.org/10.1112/S0010437X11007226.
ieee: G. Brown, M. Kerber, and M. Reid, “Fano 3 folds in codimension 4 Tom and Jerry
Part I,” Compositio Mathematica, vol. 148, no. 4. Cambridge University
Press, pp. 1171–1194, 2012.
ista: Brown G, Kerber M, Reid M. 2012. Fano 3 folds in codimension 4 Tom and Jerry
Part I. Compositio Mathematica. 148(4), 1171–1194.
mla: Brown, Gavin, et al. “Fano 3 Folds in Codimension 4 Tom and Jerry Part I.”
Compositio Mathematica, vol. 148, no. 4, Cambridge University Press, 2012,
pp. 1171–94, doi:10.1112/S0010437X11007226.
short: G. Brown, M. Kerber, M. Reid, Compositio Mathematica 148 (2012) 1171–1194.
date_created: 2018-12-11T12:01:30Z
date_published: 2012-07-01T00:00:00Z
date_updated: 2021-01-12T07:41:12Z
day: '01'
department:
- _id: HeEd
doi: 10.1112/S0010437X11007226
intvolume: ' 148'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1009.4313
month: '07'
oa: 1
oa_version: Preprint
page: 1171 - 1194
publication: Compositio Mathematica
publication_status: published
publisher: Cambridge University Press
publist_id: '3579'
quality_controlled: '1'
scopus_import: 1
status: public
title: Fano 3 folds in codimension 4 Tom and Jerry Part I
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 148
year: '2012'
...
---
_id: '3133'
abstract:
- lang: eng
text: 'This note contributes to the point calculus of persistent homology by extending
Alexander duality from spaces to real-valued functions. Given a perfect Morse
function f: S n+1 →[0, 1 and a decomposition S n+1 = U ∪ V into two (n + 1)-manifolds
with common boundary M, we prove elementary relationships between the persistence
diagrams of f restricted to U, to V, and to M. '
acknowledgement: "his research is partially supported by the National Science Foundation
(NSF) under grant DBI-0820624, the European Science Foundation under the Research
Networking Programme, and the Russian Government Project 11.G34.31.0053.\r\nThe
authors thank an anonymous referee for suggesting the simplified proof of the Contravariant
PE Theorem given in this paper. They also thank Frederick Cohen, Yuriy Mileyko and
Amit Patel for helpful discussions."
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Edelsbrunner H, Kerber M. Alexander duality for functions: The persistent
behavior of land and water and shore. In: Proceedings of the Twenty-Eighth
Annual Symposium on Computational Geometry . ACM; 2012:249-258. doi:10.1145/2261250.2261287'
apa: 'Edelsbrunner, H., & Kerber, M. (2012). Alexander duality for functions:
The persistent behavior of land and water and shore. In Proceedings of the
twenty-eighth annual symposium on Computational geometry (pp. 249–258). Chapel
Hill, NC, USA: ACM. https://doi.org/10.1145/2261250.2261287'
chicago: 'Edelsbrunner, Herbert, and Michael Kerber. “Alexander Duality for Functions:
The Persistent Behavior of Land and Water and Shore.” In Proceedings of the
Twenty-Eighth Annual Symposium on Computational Geometry , 249–58. ACM, 2012.
https://doi.org/10.1145/2261250.2261287.'
ieee: 'H. Edelsbrunner and M. Kerber, “Alexander duality for functions: The persistent
behavior of land and water and shore,” in Proceedings of the twenty-eighth
annual symposium on Computational geometry , Chapel Hill, NC, USA, 2012, pp.
249–258.'
ista: 'Edelsbrunner H, Kerber M. 2012. Alexander duality for functions: The persistent
behavior of land and water and shore. Proceedings of the twenty-eighth annual
symposium on Computational geometry . SCG: Symposium on Computational Geometry,
249–258.'
mla: 'Edelsbrunner, Herbert, and Michael Kerber. “Alexander Duality for Functions:
The Persistent Behavior of Land and Water and Shore.” Proceedings of the Twenty-Eighth
Annual Symposium on Computational Geometry , ACM, 2012, pp. 249–58, doi:10.1145/2261250.2261287.'
short: H. Edelsbrunner, M. Kerber, in:, Proceedings of the Twenty-Eighth Annual
Symposium on Computational Geometry , ACM, 2012, pp. 249–258.
conference:
end_date: 2012-06-20
location: Chapel Hill, NC, USA
name: 'SCG: Symposium on Computational Geometry'
start_date: 2012-06-17
date_created: 2018-12-11T12:01:35Z
date_published: 2012-06-20T00:00:00Z
date_updated: 2021-01-12T07:41:17Z
day: '20'
department:
- _id: HeEd
doi: 10.1145/2261250.2261287
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1109.5052
month: '06'
oa: 1
oa_version: Preprint
page: 249 - 258
publication: 'Proceedings of the twenty-eighth annual symposium on Computational geometry '
publication_status: published
publisher: ACM
publist_id: '3564'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Alexander duality for functions: The persistent behavior of land and water
and shore'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '3256'
abstract:
- lang: eng
text: We use a distortion to define the dual complex of a cubical subdivision of
ℝ n as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated
by the topological analysis of high-dimensional digital image data, we consider
such subdivisions defined by generalizations of quad- and oct-trees to n dimensions.
Assuming the subdivision is balanced, we show that mapping each vertex to the
center of the corresponding n-cube gives a geometric realization of the dual complex
in ℝ n.
acknowledgement: This research is partially supported by the Defense Advanced Research
Projects Agency (DARPA) under grants HR0011-05-1-0057 and HR0011-09-0065 as well
as the National Science Foundation (NSF) under grant DBI-0820624.
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: Edelsbrunner H, Kerber M. Dual complexes of cubical subdivisions of ℝn. Discrete
& Computational Geometry. 2012;47(2):393-414. doi:10.1007/s00454-011-9382-4
apa: Edelsbrunner, H., & Kerber, M. (2012). Dual complexes of cubical subdivisions
of ℝn. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-011-9382-4
chicago: Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions
of ℝn.” Discrete & Computational Geometry. Springer, 2012. https://doi.org/10.1007/s00454-011-9382-4.
ieee: H. Edelsbrunner and M. Kerber, “Dual complexes of cubical subdivisions of
ℝn,” Discrete & Computational Geometry, vol. 47, no. 2. Springer, pp.
393–414, 2012.
ista: Edelsbrunner H, Kerber M. 2012. Dual complexes of cubical subdivisions of
ℝn. Discrete & Computational Geometry. 47(2), 393–414.
mla: Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions
of ℝn.” Discrete & Computational Geometry, vol. 47, no. 2, Springer,
2012, pp. 393–414, doi:10.1007/s00454-011-9382-4.
short: H. Edelsbrunner, M. Kerber, Discrete & Computational Geometry 47 (2012)
393–414.
date_created: 2018-12-11T12:02:17Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2021-01-12T07:42:10Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/s00454-011-9382-4
file:
- access_level: open_access
checksum: 76486f3b2c9e7fd81342f3832ca387e7
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:15Z
date_updated: 2020-07-14T12:46:05Z
file_id: '4675'
file_name: IST-2016-543-v1+1_2012-J-08-HierarchyCubeComplex.pdf
file_size: 203636
relation: main_file
file_date_updated: 2020-07-14T12:46:05Z
has_accepted_license: '1'
intvolume: ' 47'
issue: '2'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 393 - 414
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '3398'
pubrep_id: '543'
quality_controlled: '1'
scopus_import: 1
status: public
title: Dual complexes of cubical subdivisions of ℝn
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 47
year: '2012'
...
---
_id: '3331'
abstract:
- lang: eng
text: Computing the topology of an algebraic plane curve C means computing a combinatorial
graph that is isotopic to C and thus represents its topology in R2. We prove that,
for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology
of the induced curve can be computed with bit operations ( indicates that we
omit logarithmic factors). Our analysis improves the previous best known complexity
bounds by a factor of n2. The improvement is based on new techniques to compute
and refine isolating intervals for the real roots of polynomials, and on the consequent
amortized analysis of the critical fibers of the algebraic curve.
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: Kerber M, Sagraloff M. A worst case bound for topology computation of algebraic
curves. Journal of Symbolic Computation. 2012;47(3):239-258. doi:10.1016/j.jsc.2011.11.001
apa: Kerber, M., & Sagraloff, M. (2012). A worst case bound for topology computation
of algebraic curves. Journal of Symbolic Computation. Elsevier. https://doi.org/10.1016/j.jsc.2011.11.001
chicago: Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology
Computation of Algebraic Curves.” Journal of Symbolic Computation. Elsevier,
2012. https://doi.org/10.1016/j.jsc.2011.11.001.
ieee: M. Kerber and M. Sagraloff, “A worst case bound for topology computation of
algebraic curves,” Journal of Symbolic Computation, vol. 47, no. 3. Elsevier,
pp. 239–258, 2012.
ista: Kerber M, Sagraloff M. 2012. A worst case bound for topology computation of
algebraic curves. Journal of Symbolic Computation. 47(3), 239–258.
mla: Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology Computation
of Algebraic Curves.” Journal of Symbolic Computation, vol. 47, no. 3,
Elsevier, 2012, pp. 239–58, doi:10.1016/j.jsc.2011.11.001.
short: M. Kerber, M. Sagraloff, Journal of Symbolic Computation 47 (2012) 239–258.
date_created: 2018-12-11T12:02:43Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2021-01-12T07:42:43Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.jsc.2011.11.001
intvolume: ' 47'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.1510
month: '03'
oa: 1
oa_version: Preprint
page: 239 - 258
publication: ' Journal of Symbolic Computation'
publication_status: published
publisher: Elsevier
publist_id: '3303'
quality_controlled: '1'
scopus_import: 1
status: public
title: A worst case bound for topology computation of algebraic curves
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 47
year: '2012'
...
---
_id: '3270'
abstract:
- lang: eng
text: 'The persistence diagram of a filtered simplicial com- plex is usually computed
by reducing the boundary matrix of the complex. We introduce a simple op- timization
technique: by processing the simplices of the complex in decreasing dimension,
we can “kill” columns (i.e., set them to zero) without reducing them. This technique
completely avoids reduction on roughly half of the columns. We demonstrate that
this idea significantly improves the running time of the reduction algorithm in
practice. We also give an output-sensitive complexity analysis for the new al-
gorithm which yields to sub-cubic asymptotic bounds under certain assumptions.'
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Chen C, Kerber M. Persistent homology computation with a twist. In: TU Dortmund;
2011:197-200.'
apa: 'Chen, C., & Kerber, M. (2011). Persistent homology computation with a
twist (pp. 197–200). Presented at the EuroCG: European Workshop on Computational
Geometry, Morschach, Switzerland: TU Dortmund.'
chicago: Chen, Chao, and Michael Kerber. “Persistent Homology Computation with a
Twist,” 197–200. TU Dortmund, 2011.
ieee: 'C. Chen and M. Kerber, “Persistent homology computation with a twist,” presented
at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland,
2011, pp. 197–200.'
ista: 'Chen C, Kerber M. 2011. Persistent homology computation with a twist. EuroCG:
European Workshop on Computational Geometry, 197–200.'
mla: Chen, Chao, and Michael Kerber. Persistent Homology Computation with a Twist.
TU Dortmund, 2011, pp. 197–200.
short: C. Chen, M. Kerber, in:, TU Dortmund, 2011, pp. 197–200.
conference:
end_date: 2011-03-30
location: Morschach, Switzerland
name: 'EuroCG: European Workshop on Computational Geometry'
start_date: 2011-03-28
date_created: 2018-12-11T12:02:22Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T07:42:17Z
day: '01'
department:
- _id: HeEd
language:
- iso: eng
month: '01'
oa_version: None
page: 197 - 200
publication_status: published
publisher: TU Dortmund
publist_id: '3376'
quality_controlled: '1'
status: public
title: Persistent homology computation with a twist
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3328'
abstract:
- lang: eng
text: 'We report on a generic uni- and bivariate algebraic kernel that is publicly
available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art
implementations on polynomials, roots of polynomial systems, and the support to
analyze algebraic curves defined by bivariate polynomials. The kernel design is
generic, that is, various number types and substeps can be exchanged. It is accompanied
with a ready-to-use interface to enable arrangements induced by algebraic curves,
that have already been used as basis for various geometric applications, as arrangements
on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel
applications: arrangements of rotated algebraic curves and Boolean set operations
on polygons bounded by segments of algebraic curves. We also provide experiments
showing that our general implementation is competitive and even often clearly
outperforms existing implementations that are explicitly tailored for specific
types of non-linear curves that are available in CGAL.'
article_processing_charge: No
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Michael
full_name: Hemmer, Michael
last_name: Hemmer
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Berberich E, Hemmer M, Kerber M. A generic algebraic kernel for non linear
geometric applications. In: ACM; 2011:179-186. doi:10.1145/1998196.1998224'
apa: 'Berberich, E., Hemmer, M., & Kerber, M. (2011). A generic algebraic kernel
for non linear geometric applications (pp. 179–186). Presented at the SCG: Symposium
on Computational Geometry, Paris, France: ACM. https://doi.org/10.1145/1998196.1998224'
chicago: Berberich, Eric, Michael Hemmer, and Michael Kerber. “A Generic Algebraic
Kernel for Non Linear Geometric Applications,” 179–86. ACM, 2011. https://doi.org/10.1145/1998196.1998224.
ieee: 'E. Berberich, M. Hemmer, and M. Kerber, “A generic algebraic kernel for non
linear geometric applications,” presented at the SCG: Symposium on Computational
Geometry, Paris, France, 2011, pp. 179–186.'
ista: 'Berberich E, Hemmer M, Kerber M. 2011. A generic algebraic kernel for non
linear geometric applications. SCG: Symposium on Computational Geometry, 179–186.'
mla: Berberich, Eric, et al. A Generic Algebraic Kernel for Non Linear Geometric
Applications. ACM, 2011, pp. 179–86, doi:10.1145/1998196.1998224.
short: E. Berberich, M. Hemmer, M. Kerber, in:, ACM, 2011, pp. 179–186.
conference:
end_date: 2011-06-15
location: Paris, France
name: 'SCG: Symposium on Computational Geometry'
start_date: 2011-06-13
date_created: 2018-12-11T12:02:42Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2021-01-12T07:42:41Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998224
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hal.inria.fr/inria-00480031/file/RR-7274.pdf
month: '06'
oa: 1
oa_version: Published Version
page: 179 - 186
publication_status: published
publisher: ACM
publist_id: '3307'
quality_controlled: '1'
scopus_import: 1
status: public
title: A generic algebraic kernel for non linear geometric applications
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3329'
abstract:
- lang: eng
text: 'We consider the offset-deconstruction problem: Given a polygonal shape Q
with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance,
as the Minkowski sum of another polygonal shape P with a disk of fixed radius?
If it does, we also seek a preferably simple-looking solution shape P; then, P''s
offset constitutes an accurate, vertex-reduced, and smoothened approximation of
Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal
shape, assuming the real-RAM model of computation. An alternative algorithm, based
purely on rational arithmetic, answers the same deconstruction problem, up to
an uncertainty parameter, and its running time depends on the parameter δ (in
addition to the other input parameters: n, δ and the radius of the disk). If the
input shape is found to be approximable, the rational-arithmetic algorithm also
computes an approximate solution shape for the problem. For convex shapes, the
complexity of the exact decision algorithm drops to O(n), which is also the time
required to compute a solution shape P with at most one more vertex than a vertex-minimal
one. Our study is motivated by applications from two different domains. However,
since the offset operation has numerous uses, we anticipate that the reverse question
that we study here will be still more broadly applicable. We present results obtained
with our implementation of the rational-arithmetic algorithm.'
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Dan
full_name: Halperin, Dan
last_name: Halperin
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Roza
full_name: Pogalnikova, Roza
last_name: Pogalnikova
citation:
ama: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate
offsets. In: Proceedings of the Twenty-Seventh Annual Symposium on Computational
Geometry. ACM; 2011:187-196. doi:10.1145/1998196.1998225'
apa: 'Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2011). Deconstructing
approximate offsets. In Proceedings of the twenty-seventh annual symposium
on Computational geometry (pp. 187–196). Paris, France: ACM. https://doi.org/10.1145/1998196.1998225'
chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing
Approximate Offsets.” In Proceedings of the Twenty-Seventh Annual Symposium
on Computational Geometry, 187–96. ACM, 2011. https://doi.org/10.1145/1998196.1998225.
ieee: E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing
approximate offsets,” in Proceedings of the twenty-seventh annual symposium
on Computational geometry, Paris, France, 2011, pp. 187–196.
ista: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. 2011. Deconstructing approximate
offsets. Proceedings of the twenty-seventh annual symposium on Computational geometry.
SCG: Symposium on Computational Geometry, 187–196.'
mla: Berberich, Eric, et al. “Deconstructing Approximate Offsets.” Proceedings
of the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011,
pp. 187–96, doi:10.1145/1998196.1998225.
short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, Proceedings of
the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp.
187–196.
conference:
end_date: 2011-06-15
location: Paris, France
name: 'SCG: Symposium on Computational Geometry'
start_date: 2011-06-13
date_created: 2018-12-11T12:02:42Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2023-02-23T11:12:57Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998225
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1109.2158
month: '06'
oa: 1
oa_version: Preprint
page: 187 - 196
publication: Proceedings of the twenty-seventh annual symposium on Computational geometry
publication_status: published
publisher: ACM
publist_id: '3306'
quality_controlled: '1'
related_material:
record:
- id: '3115'
relation: later_version
status: public
scopus_import: 1
status: public
title: Deconstructing approximate offsets
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3330'
abstract:
- lang: eng
text: We consider the problem of approximating all real roots of a square-free polynomial
f. Given isolating intervals, our algorithm refines each of them to a width at
most 2-L, that is, each of the roots is approximated to L bits after the binary
point. Our method provides a certified answer for arbitrary real polynomials,
only requiring finite approximations of the polynomial coefficient and choosing
a suitable working precision adaptively. In this way, we get a correct algorithm
that is simple to implement and practically efficient. Our algorithm uses the
quadratic interval refinement method; we adapt that method to be able to cope
with inaccuracies when evaluating f, without sacrificing its quadratic convergence
behavior. We prove a bound on the bit complexity of our algorithm in terms of
degree, coefficient size and discriminant. Our bound improves previous work on
integer polynomials by a factor of deg f and essentially matches best known theoretical
bounds on root approximation which are obtained by very sophisticated algorithms.
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: 'Kerber M, Sagraloff M. Root refinement for real polynomials. In: Springer;
2011:209-216. doi:10.1145/1993886.1993920'
apa: 'Kerber, M., & Sagraloff, M. (2011). Root refinement for real polynomials
(pp. 209–216). Presented at the ISSAC: International Symposium on Symbolic and
Algebraic Computation, California, USA: Springer. https://doi.org/10.1145/1993886.1993920'
chicago: Kerber, Michael, and Michael Sagraloff. “Root Refinement for Real Polynomials,”
209–16. Springer, 2011. https://doi.org/10.1145/1993886.1993920.
ieee: 'M. Kerber and M. Sagraloff, “Root refinement for real polynomials,” presented
at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California,
USA, 2011, pp. 209–216.'
ista: 'Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC:
International Symposium on Symbolic and Algebraic Computation, 209–216.'
mla: Kerber, Michael, and Michael Sagraloff. Root Refinement for Real Polynomials.
Springer, 2011, pp. 209–16, doi:10.1145/1993886.1993920.
short: M. Kerber, M. Sagraloff, in:, Springer, 2011, pp. 209–216.
conference:
end_date: 2011-06-11
location: California, USA
name: 'ISSAC: International Symposium on Symbolic and Algebraic Computation'
start_date: 2011-06-08
date_created: 2018-12-11T12:02:43Z
date_published: 2011-06-08T00:00:00Z
date_updated: 2021-01-12T07:42:42Z
day: '08'
department:
- _id: HeEd
doi: 10.1145/1993886.1993920
external_id:
arxiv:
- '1104.1362'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.1362
month: '06'
oa: 1
oa_version: Preprint
page: 209 - 216
publication_status: published
publisher: Springer
publist_id: '3304'
quality_controlled: '1'
scopus_import: 1
status: public
title: Root refinement for real polynomials
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3332'
abstract:
- lang: eng
text: Given an algebraic hypersurface O in ℝd, how many simplices are necessary
for a simplicial complex isotopic to O? We address this problem and the variant
where all vertices of the complex must lie on O. We give asymptotically tight
worst-case bounds for algebraic plane curves. Our results gradually improve known
bounds in higher dimensions; however, the question for tight bounds remains unsolved
for d ≥ 3.
article_processing_charge: No
article_type: original
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: Kerber M, Sagraloff M. A note on the complexity of real algebraic hypersurfaces.
Graphs and Combinatorics. 2011;27(3):419-430. doi:10.1007/s00373-011-1020-7
apa: Kerber, M., & Sagraloff, M. (2011). A note on the complexity of real algebraic
hypersurfaces. Graphs and Combinatorics. Springer. https://doi.org/10.1007/s00373-011-1020-7
chicago: Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real
Algebraic Hypersurfaces.” Graphs and Combinatorics. Springer, 2011. https://doi.org/10.1007/s00373-011-1020-7.
ieee: M. Kerber and M. Sagraloff, “A note on the complexity of real algebraic hypersurfaces,”
Graphs and Combinatorics, vol. 27, no. 3. Springer, pp. 419–430, 2011.
ista: Kerber M, Sagraloff M. 2011. A note on the complexity of real algebraic hypersurfaces.
Graphs and Combinatorics. 27(3), 419–430.
mla: Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real Algebraic
Hypersurfaces.” Graphs and Combinatorics, vol. 27, no. 3, Springer, 2011,
pp. 419–30, doi:10.1007/s00373-011-1020-7.
short: M. Kerber, M. Sagraloff, Graphs and Combinatorics 27 (2011) 419–430.
date_created: 2018-12-11T12:02:43Z
date_published: 2011-03-17T00:00:00Z
date_updated: 2021-01-12T07:42:43Z
day: '17'
ddc:
- '500'
department:
- _id: HeEd
doi: 10.1007/s00373-011-1020-7
file:
- access_level: open_access
checksum: a63a1e3e885dcc68f1e3dea68dfbe213
content_type: application/pdf
creator: dernst
date_created: 2020-05-19T16:11:36Z
date_updated: 2020-07-14T12:46:08Z
file_id: '7869'
file_name: 2011_GraphsCombi_Kerber.pdf
file_size: 143976
relation: main_file
file_date_updated: 2020-07-14T12:46:08Z
has_accepted_license: '1'
intvolume: ' 27'
issue: '3'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 419 - 430
publication: Graphs and Combinatorics
publication_status: published
publisher: Springer
publist_id: '3301'
quality_controlled: '1'
scopus_import: 1
status: public
title: A note on the complexity of real algebraic hypersurfaces
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2011'
...
---
_id: '3367'
abstract:
- lang: eng
text: In this paper, we present the first output-sensitive algorithm to compute
the persistence diagram of a filtered simplicial complex. For any Γ>0, it returns
only those homology classes with persistence at least Γ. Instead of the classical
reduction via column operations, our algorithm performs rank computations on submatrices
of the boundary matrix. For an arbitrary constant δ ∈ (0,1), the running time
is O(C(1-δ)ΓR(n)log n), where C(1-δ)Γ is the number of homology classes with persistence
at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity
of computing the rank of an n x n matrix with O(n) nonzero entries. Depending
on the choice of the rank algorithm, this yields a deterministic O(C(1-δ)Γn2.376)
algorithm, a O(C(1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+ε) Monte-Carlo
algorithm for an arbitrary ε>0.
article_processing_charge: No
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Chen C, Kerber M. An output sensitive algorithm for persistent homology. In:
ACM; 2011:207-216. doi:10.1145/1998196.1998228'
apa: 'Chen, C., & Kerber, M. (2011). An output sensitive algorithm for persistent
homology (pp. 207–216). Presented at the SoCG: Symposium on Computational Geometry,
Paris, France: ACM. https://doi.org/10.1145/1998196.1998228'
chicago: Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent
Homology,” 207–16. ACM, 2011. https://doi.org/10.1145/1998196.1998228.
ieee: 'C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,”
presented at the SoCG: Symposium on Computational Geometry, Paris, France, 2011,
pp. 207–216.'
ista: 'Chen C, Kerber M. 2011. An output sensitive algorithm for persistent homology.
SoCG: Symposium on Computational Geometry, 207–216.'
mla: Chen, Chao, and Michael Kerber. An Output Sensitive Algorithm for Persistent
Homology. ACM, 2011, pp. 207–16, doi:10.1145/1998196.1998228.
short: C. Chen, M. Kerber, in:, ACM, 2011, pp. 207–216.
conference:
end_date: 2011-06-15
location: Paris, France
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2011-06-13
date_created: 2018-12-11T12:02:56Z
date_published: 2011-06-13T00:00:00Z
date_updated: 2023-02-23T11:05:04Z
day: '13'
department:
- _id: HeEd
doi: 10.1145/1998196.1998228
language:
- iso: eng
month: '06'
oa_version: None
page: 207 - 216
publication_status: published
publisher: ACM
publist_id: '3245'
quality_controlled: '1'
related_material:
record:
- id: '2939'
relation: later_version
status: public
scopus_import: 1
status: public
title: An output sensitive algorithm for persistent homology
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2011'
...
---
_id: '3796'
abstract:
- lang: eng
text: We address the problem of covering ℝ n with congruent balls, while minimizing
the number of balls that contain an average point. Considering the 1-parameter
family of lattices defined by stretching or compressing the integer grid in diagonal
direction, we give a closed formula for the covering density that depends on the
distortion parameter. We observe that our family contains the thinnest lattice
coverings in dimensions 2 to 5. We also consider the problem of packing congruent
balls in ℝ n , for which we give a closed formula for the packing density as well.
Again we observe that our family contains optimal configurations, this time densest
packings in dimensions 2 and 3.
alternative_title:
- LNCS
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: 'Edelsbrunner H, Kerber M. Covering and packing with spheres by diagonal distortion
in R^n. In: Calude C, Rozenberg G, Salomaa A, eds. Rainbow of Computer Science.
Vol 6570. Dedicated to Hermann Maurer on the Occasion of His 70th Birthday. Springer;
2011:20-35. doi:10.1007/978-3-642-19391-0_2'
apa: Edelsbrunner, H., & Kerber, M. (2011). Covering and packing with spheres
by diagonal distortion in R^n. In C. Calude, G. Rozenberg, & A. Salomaa (Eds.),
Rainbow of Computer Science (Vol. 6570, pp. 20–35). Springer. https://doi.org/10.1007/978-3-642-19391-0_2
chicago: Edelsbrunner, Herbert, and Michael Kerber. “Covering and Packing with Spheres
by Diagonal Distortion in R^n.” In Rainbow of Computer Science, edited
by Cristian Calude, Grzegorz Rozenberg, and Arto Salomaa, 6570:20–35. Dedicated
to Hermann Maurer on the Occasion of His 70th Birthday. Springer, 2011. https://doi.org/10.1007/978-3-642-19391-0_2.
ieee: H. Edelsbrunner and M. Kerber, “Covering and packing with spheres by diagonal
distortion in R^n,” in Rainbow of Computer Science, vol. 6570, C. Calude,
G. Rozenberg, and A. Salomaa, Eds. Springer, 2011, pp. 20–35.
ista: 'Edelsbrunner H, Kerber M. 2011.Covering and packing with spheres by diagonal
distortion in R^n. In: Rainbow of Computer Science. LNCS, vol. 6570, 20–35.'
mla: Edelsbrunner, Herbert, and Michael Kerber. “Covering and Packing with Spheres
by Diagonal Distortion in R^n.” Rainbow of Computer Science, edited by
Cristian Calude et al., vol. 6570, Springer, 2011, pp. 20–35, doi:10.1007/978-3-642-19391-0_2.
short: H. Edelsbrunner, M. Kerber, in:, C. Calude, G. Rozenberg, A. Salomaa (Eds.),
Rainbow of Computer Science, Springer, 2011, pp. 20–35.
date_created: 2018-12-11T12:05:13Z
date_published: 2011-05-03T00:00:00Z
date_updated: 2021-01-12T07:52:15Z
day: '03'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/978-3-642-19391-0_2
editor:
- first_name: Cristian
full_name: Calude, Cristian
last_name: Calude
- first_name: Grzegorz
full_name: Rozenberg, Grzegorz
last_name: Rozenberg
- first_name: Arto
full_name: Salomaa, Arto
last_name: Salomaa
file:
- access_level: open_access
checksum: aaf22b4d7bd4277ffe8db532119cf474
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:42Z
date_updated: 2020-07-14T12:46:16Z
file_id: '4640'
file_name: IST-2016-539-v1+1_2011-B-01-CoveringPacking.pdf
file_size: 436875
relation: main_file
file_date_updated: 2020-07-14T12:46:16Z
has_accepted_license: '1'
intvolume: ' 6570'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Submitted Version
page: 20 - 35
publication: Rainbow of Computer Science
publication_status: published
publisher: Springer
publist_id: '2427'
pubrep_id: '539'
quality_controlled: '1'
series_title: Dedicated to Hermann Maurer on the Occasion of His 70th Birthday
status: public
title: Covering and packing with spheres by diagonal distortion in R^n
type: book_chapter
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6570
year: '2011'
...
---
_id: '3849'
abstract:
- lang: eng
text: Using ideas from persistent homology, the robustness of a level set of a real-valued
function is defined in terms of the magnitude of the perturbation necessary to
kill the classes. Prior work has shown that the homology and robustness information
can be read off the extended persistence diagram of the function. This paper extends
these results to a non-uniform error model in which perturbations vary in their
magnitude across the domain.
alternative_title:
- LNCS
author:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Amit
full_name: Patel, Amit
id: 34A254A0-F248-11E8-B48F-1D18A9856A87
last_name: Patel
citation:
ama: 'Bendich P, Edelsbrunner H, Kerber M, Patel A. Persistent homology under non-uniform
error. In: Vol 6281. Springer; 2010:12-23. doi:10.1007/978-3-642-15155-2_2'
apa: 'Bendich, P., Edelsbrunner, H., Kerber, M., & Patel, A. (2010). Persistent
homology under non-uniform error (Vol. 6281, pp. 12–23). Presented at the MFCS:
Mathematical Foundations of Computer Science, Brno, Czech Republic: Springer.
https://doi.org/10.1007/978-3-642-15155-2_2'
chicago: Bendich, Paul, Herbert Edelsbrunner, Michael Kerber, and Amit Patel. “Persistent
Homology under Non-Uniform Error,” 6281:12–23. Springer, 2010. https://doi.org/10.1007/978-3-642-15155-2_2.
ieee: 'P. Bendich, H. Edelsbrunner, M. Kerber, and A. Patel, “Persistent homology
under non-uniform error,” presented at the MFCS: Mathematical Foundations of Computer
Science, Brno, Czech Republic, 2010, vol. 6281, pp. 12–23.'
ista: 'Bendich P, Edelsbrunner H, Kerber M, Patel A. 2010. Persistent homology under
non-uniform error. MFCS: Mathematical Foundations of Computer Science, LNCS, vol.
6281, 12–23.'
mla: Bendich, Paul, et al. Persistent Homology under Non-Uniform Error. Vol.
6281, Springer, 2010, pp. 12–23, doi:10.1007/978-3-642-15155-2_2.
short: P. Bendich, H. Edelsbrunner, M. Kerber, A. Patel, in:, Springer, 2010, pp.
12–23.
conference:
end_date: 2010-08-27
location: Brno, Czech Republic
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2010-08-23
date_created: 2018-12-11T12:05:30Z
date_published: 2010-08-10T00:00:00Z
date_updated: 2021-01-12T07:52:38Z
day: '10'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/978-3-642-15155-2_2
file:
- access_level: open_access
checksum: af61e1c2bb42f3d556179d4692caeb1b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:13Z
date_updated: 2020-07-14T12:46:17Z
file_id: '4994'
file_name: IST-2016-537-v1+1_2010-P-05-NonuniformError.pdf
file_size: 142357
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 6281'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 12 - 23
publication_status: published
publisher: Springer
publist_id: '2333'
pubrep_id: '537'
quality_controlled: '1'
scopus_import: 1
status: public
title: Persistent homology under non-uniform error
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6281
year: '2010'
...
---
_id: '3850'
abstract:
- lang: eng
text: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance
ε in Hausdorff distance, as the Minkowski sum of another polygonal shape with
a disk of fixed radius? If it does, we also seek a preferably simple solution
shape P;P’s offset constitutes an accurate, vertex-reduced, and smoothened approximation
of Q. We give a decision algorithm for fixed radius in O(nlogn) time that handles
any polygonal shape. For convex shapes, the complexity drops to O(n), which is
also the time required to compute a solution shape P with at most one more vertex
than a vertex-minimal one.
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Dan
full_name: Halperin, Dan
last_name: Halperin
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Roza
full_name: Pogalnikova, Roza
last_name: Pogalnikova
citation:
ama: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. Polygonal reconstruction
from approximate offsets. In: TU Dortmund; 2010:12-23.'
apa: 'Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2010). Polygonal
reconstruction from approximate offsets (pp. 12–23). Presented at the EuroCG:
European Workshop on Computational Geometry, Dortmund, Germany: TU Dortmund.'
chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Polygonal
Reconstruction from Approximate Offsets,” 12–23. TU Dortmund, 2010.
ieee: 'E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Polygonal reconstruction
from approximate offsets,” presented at the EuroCG: European Workshop on Computational
Geometry, Dortmund, Germany, 2010, pp. 12–23.'
ista: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. 2010. Polygonal reconstruction
from approximate offsets. EuroCG: European Workshop on Computational Geometry,
12–23.'
mla: Berberich, Eric, et al. Polygonal Reconstruction from Approximate Offsets.
TU Dortmund, 2010, pp. 12–23.
short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, TU Dortmund, 2010,
pp. 12–23.
conference:
end_date: 2010-03-24
location: Dortmund, Germany
name: 'EuroCG: European Workshop on Computational Geometry'
start_date: 2010-03-22
date_created: 2018-12-11T12:05:30Z
date_published: 2010-01-01T00:00:00Z
date_updated: 2021-01-12T07:52:39Z
day: '01'
department:
- _id: HeEd
language:
- iso: eng
month: '01'
oa_version: None
page: 12 - 23
publication_status: published
publisher: TU Dortmund
publist_id: '2334'
quality_controlled: '1'
status: public
title: Polygonal reconstruction from approximate offsets
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2010'
...
---
_id: '3901'
abstract:
- lang: eng
text: We are interested in 3-dimensional images given as arrays of voxels with intensity
values. Extending these values to acontinuous function, we study the robustness
of homology classes in its level and interlevel sets, that is, the amount of perturbationneeded
to destroy these classes. The structure of the homology classes and their robustness,
over all level and interlevel sets, can bevisualized by a triangular diagram of
dots obtained by computing the extended persistence of the function. We give a
fast hierarchicalalgorithm using the dual complexes of oct-tree approximations
of the function. In addition, we show that for balanced oct-trees, thedual complexes
are geometrically realized in $R^3$ and can thus be used to construct level and
interlevel sets. We apply these tools tostudy 3-dimensional images of plant root
systems.
author:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
citation:
ama: Bendich P, Edelsbrunner H, Kerber M. Computing robustness and persistence for
images. IEEE Transactions of Visualization and Computer Graphics. 2010;16(6):1251-1260.
doi:10.1109/TVCG.2010.139
apa: Bendich, P., Edelsbrunner, H., & Kerber, M. (2010). Computing robustness
and persistence for images. IEEE Transactions of Visualization and Computer
Graphics. IEEE. https://doi.org/10.1109/TVCG.2010.139
chicago: Bendich, Paul, Herbert Edelsbrunner, and Michael Kerber. “Computing Robustness
and Persistence for Images.” IEEE Transactions of Visualization and Computer
Graphics. IEEE, 2010. https://doi.org/10.1109/TVCG.2010.139.
ieee: P. Bendich, H. Edelsbrunner, and M. Kerber, “Computing robustness and persistence
for images,” IEEE Transactions of Visualization and Computer Graphics,
vol. 16, no. 6. IEEE, pp. 1251–1260, 2010.
ista: Bendich P, Edelsbrunner H, Kerber M. 2010. Computing robustness and persistence
for images. IEEE Transactions of Visualization and Computer Graphics. 16(6), 1251–1260.
mla: Bendich, Paul, et al. “Computing Robustness and Persistence for Images.” IEEE
Transactions of Visualization and Computer Graphics, vol. 16, no. 6, IEEE,
2010, pp. 1251–60, doi:10.1109/TVCG.2010.139.
short: P. Bendich, H. Edelsbrunner, M. Kerber, IEEE Transactions of Visualization
and Computer Graphics 16 (2010) 1251–1260.
date_created: 2018-12-11T12:05:47Z
date_published: 2010-10-28T00:00:00Z
date_updated: 2021-01-12T07:53:04Z
day: '28'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1109/TVCG.2010.139
file:
- access_level: open_access
checksum: f6d813c04f4b46023cec6b9a17f15472
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:10Z
date_updated: 2020-07-14T12:46:21Z
file_id: '5262'
file_name: IST-2016-536-v1+1_2010-J-02-PersistenceforImages.pdf
file_size: 721994
relation: main_file
file_date_updated: 2020-07-14T12:46:21Z
has_accepted_license: '1'
intvolume: ' 16'
issue: '6'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 1251 - 1260
publication: IEEE Transactions of Visualization and Computer Graphics
publication_status: published
publisher: IEEE
publist_id: '2253'
pubrep_id: '536'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing robustness and persistence for images
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2010'
...