@article{21407, abstract = {This note proves that only a linear number of holes in a Cech complex of n points in R^d can persist over an interval of constant length. Specifically, for any fixed dimension p < d and fixed ε > 0, the number of p-dimensional holes in the ˇ Cech complex at radius 1 that persist to radius 1+ε is bounded above by a constant times n,where n is the number of points. The proof uses a packing argument supported by relating theCˇ ech complexes with corresponding snap complexes over the cells in a partition of space. The argument is self-contained and elementary, relying on geometric and combinatorial constructions rather than on the existing theory of sparse approximations or interleavings. The bound also applies to Alpha complexes and Vietoris–Rips complexes. While our result can be inferred from prior work on sparse filtrations, to our knowledge, no explicit statement or direct proof of this bound appears in the literature.}, author = {Edelsbrunner, Herbert and Kahle, Matthew and Kanazawa, Shu}, issn = {2367-1734}, journal = {Journal of Applied and Computational Topology}, publisher = {Springer Nature}, title = {{Maximum persistent Betti numbers of Čech complexes}}, doi = {10.1007/s41468-026-00233-3}, volume = {10}, year = {2026}, } @article{20456, abstract = {Given a locally finite set A⊆Rd and a coloring χ:A→{0,1,…,s}, we introduce the chromatic Delaunay mosaic of χ, which is a Delaunay mosaic in Rs+d that represents how points of different colors mingle. Our main results are bounds on the size of the chromatic Delaunay mosaic, in which we assume that d and s are constants. For example, if A is finite with n=#A, and the coloring is random, then the chromatic Delaunay mosaic has O(n⌈d/2⌉) cells in expectation. In contrast, for Delone sets and Poisson point processes in Rd, the expected number of cells within a closed ball is only a constant times the number of points in this ball. Furthermore, in R2 all colorings of a dense set of n points have chromatic Delaunay mosaics of size O(n). This encourages the use of chromatic Delaunay mosaics in applications.}, author = {Biswas, Ranita and Cultrera di Montesano, Sebastiano and Draganov, Ondrej and Edelsbrunner, Herbert and Saghafian, Morteza}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {24--47}, publisher = {Springer Nature}, title = {{On the size of chromatic Delaunay mosaics}}, doi = {10.1007/s00454-025-00778-7}, volume = {75}, year = {2026}, } @article{21931, abstract = {In 1873, James C. Maxwell conjectured that the electric field generated by n point charges in generic position has at most (n-1)^2 isolated zeroes. The first (nonoptimal) upper bound was only obtained in 2007 by Gabrielov, Novikov, and Shapiro, who also posed two additional interesting conjectures. In this article, we give the best upper bound known to date on the number of zeroes of the electric field, and construct a counterexample to Conjecture 1.8 by Gabrielov, Novikov, and Shapiro that the number of equilibria cannot exceed those of the distance function defined by the unit point charges. Finally, we note that it is quite possible that Maxwell's quadratic upper bound is not tight, so it is prudent to find lower bounds. Hence, we also explore examples and construct configurations of charges achieving the highest ratios of the number of electric field zeroes by point charges found to this day.}, author = {Edelsbrunner, Herbert and Fillmore, Christopher D and Oliveira, Goncalo}, issn = {1460-244X}, journal = {Proceedings of the London Mathematical Society}, number = {5}, publisher = {Wiley}, title = {{Counting equilibria of the electrostatic potential}}, doi = {10.1112/plms.70163}, volume = {132}, year = {2026}, } @article{20490, abstract = {We study flips in hypertriangulations of planar points sets. Here a level-k hypertriangulation of n points in the plane is a subdivision induced by the projection of a k-hypersimplex, which is the convex hull of the barycenters of the (k-1)-dimensional faces of the standard (n-1)-simplex. In particular, we introduce four types of flips and prove that the level-2 hypertriangulations are connected by these flips. }, author = {Edelsbrunner, Herbert and Garber, Alexey and Ghafari, Mohadese and Heiss, Teresa and Saghafian, Morteza}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{Flips in two-dimensional hypertriangulations}}, doi = {10.1016/j.ejc.2025.104248}, volume = {132}, year = {2026}, } @inproceedings{22299, abstract = {The depth poset of a filtered Lefschetz complex reflects the dependencies between the cancellations of different shallow birth-death pairs. Using the fast algorithms for computing the depth poset in [Edelsbrunner et al., 2026] and for updating the persistence diagram under transpositions in [Cohen-Steiner et al., 2006], we give a complete case analysis of how transpositions of cells in the filter affect the depth poset. In addition, we present statistics on the depth poset for random point data and its sensitivity to the transpositions that occur in random straight-line homotopies.}, author = {Edelsbrunner, Herbert and Lipiński, Michał and Mrozek, Marian and Soriano Trigueros, Manuel and Zimin, Fedor}, booktitle = {42nd International Symposium on Computational Geometry}, isbn = {9783959774185}, issn = {1868-8969}, keywords = {Algebraic topology, Lefschetz complexes, persistent homology, vines and vineyards, birth-death pairs, shallow pairs, relations, partial orders, transpositions, Theory of computation → Computational geometry}, location = {New Brunswick, NJ, United States}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The depth poset under transpositions in the filter}}, doi = {10.4230/LIPICS.SOCG.2026.41}, volume = {367}, year = {2026}, } @article{20657, 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². }, author = {Edelsbrunner, Herbert and Pach, János}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, pages = {597--624}, publisher = {Springer Nature}, title = {{Maximum Betti numbers of Čech complexes}}, doi = {10.1007/s00454-025-00796-5}, volume = {75}, year = {2026}, } @article{20585, abstract = {Motivated by applications in medical sciences, we study finite chromatic sets in Euclidean space from a topological perspective. Based on the persistent homology for images, kernels and cokernels, we design provably stable homological quantifiers that describe the geometric micro- and macro-structure of how the color classes mingle. These can be efficiently computed using chromatic variants of Delaunay and alpha complexes, and code that does these computations is provided.}, author = {Cultrera di Montesano, Sebastiano and Draganov, Ondrej and Edelsbrunner, Herbert and Saghafian, Morteza}, issn = {2639-8001}, journal = {Foundations of Data Science}, keywords = {Topological data analysis, Delaunay mosaic, alpha complex, chromatic sets, persistent homology, kernel/image/cokernel persistent homology, radius function, discrete Morse theory, exact sequences}, pages = {30--62}, publisher = {AIMS}, title = {{Chromatic alpha complexes}}, doi = {10.3934/fods.2025003}, volume = {8}, year = {2026}, } @article{18626, abstract = {The local angle property of the (order-1) Delaunay triangulations of a generic set in R2 asserts that the sum of two angles opposite a common edge is less than π. This paper extends this property to higher order and uses it to generalize two classic properties from order-1 to order-2: (1) among the complete level-2 hypertriangulations of a generic point set in R2, the order-2 Delaunay triangulation lexicographically maximizes the sorted angle vector; (2) among the maximal level-2 hypertriangulations of a generic point set in R2, the order-2 Delaunay triangulation is the only one that has the local angle property. We also use our method of establishing (2) to give a new short proof of the angle vector optimality for the (order-1) Delaunay triangulation. For order-1, both properties have been instrumental in numerous applications of Delaunay triangulations, and we expect that their generalization will make order-2 Delaunay triangulations more attractive to applications as well.}, author = {Edelsbrunner, Herbert and Garber, Alexey and Saghafian, Morteza}, issn = {1090-2082}, journal = {Advances in Mathematics}, publisher = {Elsevier}, title = {{Order-2 Delaunay triangulations optimize angles}}, doi = {10.1016/j.aim.2024.110055}, volume = {461}, year = {2025}, } @inproceedings{20005, abstract = {We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose exactly k points of A. We extend this result to the cases in which the points are weighted, and when A contains only finitely many points in ℝ^d or in 𝕊^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.}, author = {Edelsbrunner, Herbert and Garber, Alexey and Saghafian, Morteza}, booktitle = {41st International Symposium on Computational Geometry}, isbn = {9783959773706}, issn = {1868-8969}, location = {Kanazawa, Japan}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{On spheres with k points inside}}, doi = {10.4230/LIPIcs.SoCG.2025.43}, volume = {332}, year = {2025}, } @inproceedings{20006, abstract = {In numerous fields, dynamic time series data require continuous updates, necessitating efficient data processing techniques for accurate analysis. This paper examines the banana tree data structure, specifically designed to efficiently maintain the multi-scale topological descriptor commonly known as persistent homology for dynamically changing time series data. We implement this data structure and conduct an experimental study to assess its properties and runtime for update operations. Our findings indicate that banana trees are highly effective with unbiased random data, outperforming state-of-the-art static algorithms in these scenarios. Additionally, our results show that real-world time series share structural properties with unbiased random walks, suggesting potential practical utility for our implementation.}, author = {Ost, Lara and Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert}, booktitle = {41st International Symposium on Computational Geometry}, isbn = {9783959773706}, issn = {1868-8969}, location = {Kanazawa, Japan}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Banana trees for the persistence in time series experimentally}}, doi = {10.4230/LIPIcs.SoCG.2025.71}, volume = {332}, year = {2025}, } @article{20293, abstract = {Motivated by questions arising at the intersection of information theory and geometry, we compare two dissimilarity measures between finite categorical distributions. One is the well-known Jensen–Shannon divergence, which is easy to compute and whose square root is a proper metric. The other is what we call the minmax divergence, which is harder to compute. Just like the Jensen–Shannon divergence, it arises naturally from the Kullback–Leibler divergence. The main contribution of this paper is a proof showing that the minmax divergence can be tightly approximated by the Jensen–Shannon divergence. The bounds suggest that the square root of the minmax divergence is a metric, and we prove that this is indeed true in the one-dimensional case. The general case remains open. Finally, we consider analogous questions in the context of another Bregman divergence and the corresponding Burbea–Rao (Jensen–Bregman) divergence.}, author = {Akopyan, Arseniy and Edelsbrunner, Herbert and Virk, Ziga and Wagner, Hubert}, issn = {1099-4300}, journal = {Entropy}, number = {8}, publisher = {MDPI}, title = {{Tight bounds between the Jensen–Shannon divergence and the minmax divergence}}, doi = {10.3390/e27080854}, volume = {27}, year = {2025}, } @inproceedings{20658, abstract = {The medial axis of a smoothly embedded surface in R^3 consists of all points for which the Euclidean distance function on the surface has at least two global minima. We generalize this notion to the mid-sphere axis, which consists of all points for which the Euclidean distance function has two interchanging saddles that swap their partners in the pairing by persistent homology. It offers a discrete-algebraic multi-scale approach to computing ridge-like structures on the surface. As a proof of concept, an algorithm that computes stair-case approximations of the mid-sphere axis is provided.}, author = {Edelsbrunner, Herbert and Stephenson, Elizabeth R and Thoresen, Martin H}, booktitle = {4th International Joint Conference on Discrete Geometry and Mathematical Morphology}, isbn = {9783032095435}, issn = {1611-3349}, location = {Groningen, The Netherlands}, pages = {133--147}, publisher = {Springer Nature}, title = {{The mid-sphere cousin of the medial axis transform}}, doi = {10.1007/978-3-032-09544-2_10}, volume = {16296}, year = {2025}, } @unpublished{21050, abstract = {In 1873, James C. Maxwell conjectured that the electric field generated by $n$ point charges in generic position has at most $(n-1)^2$ isolated zeroes. The first (non-optimal) upper bound was only obtained in 2007 by Gabrielov, Novikov and Shapiro, who also posed two additional interesting conjectures. In this article, we give the best upper bound known to date on the number of zeroes of the electric field, and construct a counterexample to a conjecture of Gabrielov, Novikov and Shapiro that the number of equilibria cannot exceed those of the distance function defined by the unit point charges. Finally, we note that it is quite possible that Maxwell's quadratic upper bound is not tight, so it is prudent to find smaller bounds. Hence, we also explore examples and construct configurations of charges achieving the highest ratios of the number of electric field zeroes by point charges found to this day.}, author = {Edelsbrunner, Herbert and Fillmore, Christopher D and Olivera, Gonçalo}, booktitle = {arXiv}, title = {{Counting equilibria of the electrostatic potential}}, doi = {10.48550/ARXIV.2501.05315}, year = {2025}, } @article{17149, abstract = {The approximation of a circle with the edges of a fine square grid distorts the perimeter by a factor about 4/Pi. We prove that this factor is the same on average (in the ergodic sense) for approximations of any rectifiable curve by the edges of any non-exotic Delaunay mosaic (known as Voronoi path), and extend the results to all dimensions, generalizing Voronoi paths to Voronoi scapes.}, author = {Edelsbrunner, Herbert and Nikitenko, Anton}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, pages = {490--499}, publisher = {Springer Nature}, title = {{Average and expected distortion of Voronoi paths and scapes}}, doi = {10.1007/s00454-024-00660-y}, volume = {73}, year = {2025}, } @unpublished{18999, abstract = {Exploring the shape of point configurations has been a key driver in the evolution of TDA (short for topological data analysis) since its infancy. This survey illustrates the recent efforts to broaden these ideas to model spatial interactions among multiple configurations, each distinguished by a color. It describes advances in this area and prepares the ground for further exploration by mentioning unresolved questions and promising research avenues while focusing on the overlap with discrete geometry.}, author = {Cultrera di Montesano, Sebastiano and Draganov, Ondrej and Edelsbrunner, Herbert and Saghafian, Morteza}, booktitle = {arXiv}, title = {{Chromatic topological data analysis}}, doi = {10.48550/ARXIV.2406.04102}, year = {2024}, } @article{14345, abstract = {For a locally finite set in R2, the order-k Brillouin tessellations form an infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely dense and generic, then the corresponding infinite sequences of minimum and maximum angles are both monotonic in k. As an example, a stationary Poisson point process in R2 is locally finite, coarsely dense, and generic with probability one. For such a set, the distributions of angles in the Voronoi tessellations, Delaunay mosaics, and Brillouin tessellations are independent of the order and can be derived from the formula for angles in order-1 Delaunay mosaics given by Miles (Math. Biosci. 6, 85–127 (1970)).}, author = {Edelsbrunner, Herbert and Garber, Alexey and Ghafari, Mohadese and Heiss, Teresa and Saghafian, Morteza}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {29--48}, publisher = {Springer Nature}, title = {{On angles in higher order Brillouin tessellations and related tilings in the plane}}, doi = {10.1007/s00454-023-00566-1}, volume = {72}, year = {2024}, } @inproceedings{17146, 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.}, author = {Edelsbrunner, Herbert and Pach, János}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, issn = {1868-8969}, location = {Athens, Greece}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Maximum Betti numbers of Čech complexes}}, doi = {10.4230/LIPIcs.SoCG.2024.53}, volume = {293}, year = {2024}, } @article{17891, abstract = {Abstract Methods used in topological data analysis naturally capture higher-order interactions in point cloud data embedded in a metric space. This methodology was recently extended to data living in an information space, by which we mean a space measured with an information theoretical distance. One such setting is a finite collection of discrete probability distributions embedded in the probability simplex measured with the relative entropy (Kullback–Leibler divergence). More generally, one can work with a Bregman divergence parameterized by a different notion of entropy. While theoretical algorithms exist for this setup, there is a paucity of implementations for exploring and comparing geometric-topological properties of various information spaces. The interest of this work is therefore twofold. First, we propose the first robust algorithms and software for geometric and topological data analysis in information space. Perhaps surprisingly, despite working with Bregman divergences, our design reuses robust libraries for the Euclidean case. Second, using the new software, we take the first steps towards understanding the geometric-topological structure of these spaces. In particular, we compare them with the more familiar spaces equipped with the Euclidean and Fisher metrics.}, author = {Edelsbrunner, Herbert and Ölsböck, Katharina and Wagner, Hubert}, issn = {1099-4300}, journal = {Entropy}, number = {8}, publisher = {MDPI}, title = {{Understanding higher-order interactions in information space}}, doi = {10.3390/e26080637}, volume = {26}, year = {2024}, } @article{17190, abstract = {For a locally finite set, 𝐴⊆ℝ𝑑 , the 𝑘 th Brillouin zone of 𝑎∈𝐴 is the region of points 𝑥∈ℝ𝑑 for which ‖𝑥−𝑎‖ is the 𝑘 th smallest among the Euclidean distances between 𝑥 and the points in 𝐴 . If 𝐴 is a lattice, the 𝑘 th Brillouin zones of the points in 𝐴 are translates of each other, and together they tile space. Depending on the value of 𝑘 , they express medium- or long-range order in the set. We study fundamental geometric and combinatorial properties of Brillouin zones, focusing on the integer lattice and its perturbations. Our results include the stability of a Brillouin zone under perturbations, a linear upper bound on the number of chambers in a zone for lattices in ℝ2 , and the convergence of the maximum volume of a chamber to zero for the integer lattice.}, author = {Edelsbrunner, Herbert and Garber, Alexey and Ghafaris, Mohadese and Heiss, Teresa and Saghafiant, Morteza and Wintraecken, Mathijs}, issn = {0895-4801}, journal = {SIAM Journal on Discrete Mathematics}, number = {2}, pages = {1784--1807}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Brillouin zones of integer lattices and their perturbations}}, doi = {10.1137/22M1489071}, volume = {38}, year = {2024}, } @inproceedings{18556, abstract = {Given a finite set, A ⊆ ℝ², and a subset, B ⊆ A, the MST-ratio is the combined length of the minimum spanning trees of B and A⧵B divided by the length of the minimum spanning tree of A. The question of the supremum, over all sets A, of the maximum, over all subsets B, is related to the Steiner ratio, and we prove this sup-max is between 2.154 and 2.427. Restricting ourselves to 2-dimensional lattices, we prove that the sup-max is 2, while the inf-max is 1.25. By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than 1.25.}, author = {Cultrera di Montesano, Sebastiano and Draganov, Ondrej and Edelsbrunner, Herbert and Saghafian, Morteza}, booktitle = {32nd International Symposium on Graph Drawing and Network Visualization}, isbn = {9783959773430}, issn = {1868-8969}, location = {Vienna, Austria}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The Euclidean MST-ratio for bi-colored lattices}}, doi = {10.4230/LIPIcs.GD.2024.3}, volume = {320}, year = {2024}, }