Maximum Betti numbers of Čech complexes

Edelsbrunner H, Pach J. 2024. Maximum Betti numbers of Čech complexes. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 53.

Download
OA 2024_LIPICS_Edelsbrunner.pdf 766.56 KB [Published Version]

Conference Paper | Published | English

Scopus indexed
Department
Series Title
LIPIcs
Abstract
The Upper Bound Theorem for convex polytopes implies that the p-th Betti number of the Čech complex of any set of N points in ℝ^d and any radius satisfies β_p = O(N^m), with m = min{p+1, ⌈d/2⌉}. We construct sets in even and odd dimensions, which prove that this upper bound is asymptotically tight. For example, we describe a set of N = 2(n+1) points in ℝ³ and two radii such that the first Betti number of the Čech complex at one radius is (n+1)² - 1, and the second Betti number of the Čech complex at the other radius is n². In particular, there is an arrangement of n contruent balls in ℝ³ that enclose a quadratic number of voids, which answers a long-standing open question in computational geometry.
Publishing Year
Date Published
2024-06-01
Proceedings Title
40th International Symposium on Computational Geometry
Acknowledgement
The first author is supported by the European Research Council (ERC), grant no. 788183, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), grant no. {I 02979-N35.} The second author is supported by the European Research Council (ERC), grant "GeoScape" and by the Hungarian Science Foundation (NKFIH), grant K-131529. Both authors are supported by the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. The authors thank Matt Kahle for communicating the question about extremal Čech complexes, Ben Schweinhart for early discussions on the linked circles construction in three dimensions, and Gábor Tardos for helpful remarks and suggestions.
Volume
293
Article Number
53
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Athens, Greece
Conference Date
2024-06-11 – 2024-06-14
ISSN
IST-REx-ID

Cite this

Edelsbrunner H, Pach J. Maximum Betti numbers of Čech complexes. In: 40th International Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.53
Edelsbrunner, H., & Pach, J. (2024). Maximum Betti numbers of Čech complexes. In 40th International Symposium on Computational Geometry (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.53
Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” In 40th International Symposium on Computational Geometry, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.53.
H. Edelsbrunner and J. Pach, “Maximum Betti numbers of Čech complexes,” in 40th International Symposium on Computational Geometry, Athens, Greece, 2024, vol. 293.
Edelsbrunner H, Pach J. 2024. Maximum Betti numbers of Čech complexes. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 53.
Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” 40th International Symposium on Computational Geometry, vol. 293, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.53.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2024-06-17
MD5 Checksum
5442d44fb89d77477a87668d6e61aac9


Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2310.14801

Search this title in

Google Scholar
ISBN Search