@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}, } @inproceedings{21410, abstract = {Given a finite set of red and blue points in R^d, the MST-ratio is defined as the total length of the Euclidean minimum spanning trees of the red points and the blue points, divided by the length of the Euclidean minimum spanning tree of their union. The MST-ratio has recently gained attention due to its direct interpretation in topological models for studying point sets with applications in spatial biology. The maximum MST-ratio of a point set is the maximum MST-ratio over all proper colorings of its points by red and blue. We prove that finding the maximum MST-ratio of a given point set is NP-hard when the dimension is part of the input. Moreover, we present a quadratic-time 3-approximation algorithm for this problem. As part of the proof, we show that in any metric space, the maximum MST-ratio is smaller than 3. Furthermore, we study the average MST-ratio over all colorings of a set of n points. We show that this average is always at least n-2/n-1, and for n random points uniformly distributed in a d-dimensional unit cube, the average tends to (math formular) in expectation as n approaches infinity.}, author = {Jabal Ameli, Afrouz and Motiei, Faezeh and Saghafian, Morteza}, booktitle = {20th International Conference and Workshops on Algorithms and Computation}, isbn = {9789819571260}, issn = {1611-3349}, location = {Perugia, Italy}, pages = {386--401}, publisher = {Springer Nature}, title = {{On the MST-ratio: Theoretical bounds and complexity of finding the maximum}}, doi = {10.1007/978-981-95-7127-7_26}, volume = {16444}, 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}, } @article{19937, abstract = {Simplets are elementary units within simplicial complexes and are fundamental for analyzing the structure of simplicial complexes. Previous efforts have mainly focused on accurately counting or approximating the number of simplets rather than studying their frequencies. However, analyzing simplet frequencies is more practical for large-scale simplicial complexes. This paper introduces the Simplet Frequency Distribution (SFD) vector, which enables the analysis of simplet frequencies in simplicial complexes. Additionally, we provide a bound on the sample complexity required to approximate the SFD vector using any uniform sampling-based algorithm accurately. We extend the definition of simplet frequency distribution to encompass simplices, allowing for the analysis of simplet frequencies within simplices of simplicial complexes. This paper introduces the Simplet Degree Vector (SDV) and the Simplet Degree Centrality (SDC), facilitating this analysis for each simplex. Furthermore, we present a bound on the sample complexity required for accurately approximating the SDV and SDC for a set of simplices using any uniform sampling-based algorithm. We also introduce algorithms for approximating SFD, geometric SFD, SDV, and SDC. We also validate the theoretical bounds with experiments on random simplicial complexes and demonstrate the practical application through a case study.}, author = {Mahini, Mohammad and Beigy, Hamid and Qadami, Salman and Saghafian, Morteza}, issn = {0020-0255}, journal = {Information Sciences}, number = {11}, publisher = {Elsevier}, title = {{Simplet-based signatures and approximation in simplicial complexes: Frequency, degree, and centrality}}, doi = {10.1016/j.ins.2025.122425}, volume = {719}, 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}, } @article{20323, abstract = {We establish several results combining discrete Morse theory and microlocal sheaf theory in the setting of finite posets and simplicial complexes. Our primary tool is a computationally tractable description of the bounded derived category of sheaves on a poset with the Alexandrov topology. We prove that each bounded complex of sheaves on a finite poset admits a unique (up to isomorphism of complexes) minimal injective resolution, and we provide algorithms for computing minimal injective resolution of an injective complex, as well as several useful functors between derived categories of sheaves. For the constant sheaf on a simplicial complex, we give asymptotically tight bounds on the complexity of computing the minimal injective resolution using those algorithms. Our main result is a novel definition of the discrete microsupport of a bounded complex of sheaves on a finite poset. We detail several foundational properties of the discrete microsupport, as well as a microlocal generalization of the discrete homological Morse theorem and Morse inequalities.}, author = {Brown, Adam and Draganov, Ondrej}, issn = {0022-4049}, journal = {Journal of Pure and Applied Algebra}, number = {10}, publisher = {Elsevier}, title = {{Discrete microlocal Morse theory}}, doi = {10.1016/j.jpaa.2025.108068}, volume = {229}, year = {2025}, } @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 = {2025}, } @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}, pages = {30--62}, publisher = {American Institute of Mathematical Sciences}, title = {{Chromatic alpha complexes}}, doi = {10.3934/fods.2025003}, volume = {8}, year = {2025}, } @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}, publisher = {Springer Nature}, title = {{Maximum Betti numbers of Čech complexes}}, doi = {10.1007/s00454-025-00796-5}, year = {2025}, } @unpublished{21016, abstract = {Motivated by applications in chemistry, we give a homlogical definition of tunnels, or more generally cobordisms, connecting disjoint parts of a cell complex. For a filtered complex, this defines a persistence module. We give a method for identifying birth and death times using kernel persistence and a matrix reduction algorithm for pairing birth and death times.}, author = {Bleile, Yossi and Fajstrup, Lisbeth and Heiss, Teresa and Svane, Anne Marie and Sørensen, Søren Strandskov}, booktitle = {arXiv}, title = {{Identifying cobordisms using kernel persistence}}, doi = {10.48550/arXiv.2505.17858}, 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}, } @article{20260, abstract = {The medial axis of a set consists of the points in the ambient space without a unique closest point in the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a skeleton topologically equivalent to the original set. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities, various prunings of the medial axis have been proposed in the computational geometry community. Here, we examine one type of pruning, called burning. Because of the good experimental results it was hoped that the burning method of simplifying the medial axis would be stable. In this work, we show a simple example that dashes such hopes. Based on Bing’s house with two rooms, we demonstrate an isotopy of a shape where the medial axis goes from collapsible to non-collapsible. More precisely, we consider the standard deformation retract from the closed ball to Bing’s house with two rooms, but stop just short of the point where Bing’s house becomes two dimensional. This way we obtain an isotopy from the 3-ball to a thickened version of Bing’s house. Under this isotopy, the medial axis goes from collapsible to non-collapsible. We stress that this isotopy can be made generic, in the sense of singularity theory, as developed by Arnol’d and Thom.}, author = {Chambers, Erin Wolf and Fillmore, Christopher D and Stephenson, Elizabeth R and Wintraecken, Mathijs}, issn = {2730-9657}, journal = {La Matematica}, pages = {811--828}, publisher = {Springer Nature}, title = {{Burning or collapsing the medial axis is unstable}}, doi = {10.1007/s44007-025-00170-0}, volume = {4}, year = {2025}, } @phdthesis{19630, abstract = {This thesis consists of three chapters, each corresponding to one publication. While each of these projects tackles a topic in a different area of research, they all share a common thread in the type of topological structure they handle - a partition of space into volumes separated by interfaces that meet in non-manifold junctions. In Chapter 2, we study clusters of soap bubbles from a simulation perspective. In particular, we develop a surface-only algorithm that couples large scale motion and shape deformation of soap bubble clusters with the small scale evolution of the thin film's thickness, which is responsible for visual phenomena like surface vortices, Newton's interference patterns, capillary waves, and deformation-dependent rupturing of films in a foam. We model film thickness as a reduced degree of freedom in the Navier-Stokes equations and from them derive three sets of equations governing normal and tangential motion of the soap film surface, as well as the evolution of the thin film thickness. We discretize these equations on a non-manifold triangle mesh, extending and adapting operators to handle complex topology. We also present an incompressible fluid solver for 2.5D films and an advection algorithm for convecting fields across non-manifold surface junctions. Our simulations enhance bubble solvers with additional effects caused by convection, rippling, draining, and evaporation of the thin film. In Chapter 3, we introduce a multi-material non-manifold mesh-based surface tracking algorithm that converts mesh defects, such as overlaps, self-intersections, and inversions into topological changes. Our algorithm generalizes prior work on manifold surface tracking with topological changes: it preserves surface features like mesh-based methods, and it robustly handles topological changes like level set methods. Our method also offers improved efficiency and robustness over the state of the art. We demonstrate the effectiveness of the approach on a range of examples, including complex soap film simulations, such as those presented in Chapter 2, but with an order of magnitude more interacting bubbles than what we could achieve before, and Boolean unions of non-manifold meshes consisting of millions of triangles. Lastly, in Chapter 4, we utilize developments in the theory of random geometric complexes facilitated by observations from Discrete Morse theory. We survey the methods and results obtained with this new approach, and discuss some of its shortcomings. We use simulations to illustrate the results and to form conjectures, getting numerical estimates for combinatorial, topological, and geometric properties of weighted and unweighted Delaunay mosaics, their dual Voronoi tessellations, and the Alpha and Wrap complexes contained in the mosaics.}, author = {Synak, Peter}, issn = {2663-337X}, pages = {106}, publisher = {Institute of Science and Technology Austria}, title = {{Methods for fluid simulation, surface tracking, and statistics of non-manifold structures}}, doi = {10.15479/AT-ISTA-19630}, year = {2025}, } @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{18097, abstract = {In our companion paper "Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds" we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample P of an input shape 𝒮 (either manifold or general set with positive reach) such that one can infer the homotopy of 𝒮 from the union of balls with some radius centred at P, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting.}, author = {Attali, Dominique and Kourimska, Hana and Fillmore, Christopher D and Ghosh, Ishika and Lieutier, Andre and Stephenson, Elizabeth R and Wintraecken, Mathijs}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, location = {Athens, Greece}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The ultimate frontier: An optimality construction for homotopy inference (media exposition)}}, doi = {10.4230/LIPIcs.SoCG.2024.87}, volume = {293}, 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}, } @article{15380, abstract = {The depth of a cell in an arrangement of n (non-vertical) great-spheres in Sd is the number of great-spheres that pass above the cell. We prove Euler-type relations, which imply extensions of the classic Dehn–Sommerville relations for convex polytopes to sublevel sets of the depth function, and we use the relations to extend the expressions for the number of faces of neighborly polytopes to the number of cells of levels in neighborly arrangements.}, author = {Biswas, Ranita and Cultrera Di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza}, issn = {2367-1734}, journal = {Journal of Applied and Computational Topology}, pages = {557--578}, publisher = {Springer Nature}, title = {{Depth in arrangements: Dehn–Sommerville–Euler relations with applications}}, doi = {10.1007/s41468-024-00173-w}, volume = {8}, year = {2024}, } @inproceedings{17144, abstract = {We prove that the medial axis of closed sets is Hausdorff stable in the following sense: Let 𝒮 ⊆ ℝ^d be a fixed closed set that contains a bounding sphere. That is, the bounding sphere is part of the set 𝒮. Consider the space of C^{1,1} diffeomorphisms of ℝ^d to itself, which keep the bounding sphere invariant. The map from this space of diffeomorphisms (endowed with a Banach norm) to the space of closed subsets of ℝ^d (endowed with the Hausdorff distance), mapping a diffeomorphism F to the closure of the medial axis of F(𝒮), is Lipschitz. This extends a previous stability result of Chazal and Soufflet on the stability of the medial axis of C² manifolds under C² ambient diffeomorphisms.}, author = {Kourimska, Hana and Lieutier, André and Wintraecken, Mathijs}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, issn = {1868-8969}, location = {Athens, Greece}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms}}, doi = {10.4230/LIPIcs.SoCG.2024.69}, volume = {293}, 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}, } @inproceedings{17170, abstract = {In this article we extend and strengthen the seminal work by Niyogi, Smale, and Weinberger on the learning of the homotopy type from a sample of an underlying space. In their work, Niyogi, Smale, and Weinberger studied samples of C² manifolds with positive reach embedded in ℝ^d. We extend their results in the following ways: - As the ambient space we consider both ℝ^d and Riemannian manifolds with lower bounded sectional curvature. - In both types of ambient spaces, we study sets of positive reach - a significantly more general setting than C² manifolds - as well as general manifolds of positive reach. - The sample P of a set (or a manifold) 𝒮 of positive reach may be noisy. We work with two one-sided Hausdorff distances - ε and δ - between P and 𝒮. We provide tight bounds in terms of ε and δ, that guarantee that there exists a parameter r such that the union of balls of radius r centred at the sample P deformation-retracts to 𝒮. We exhibit their tightness by an explicit construction. We carefully distinguish the roles of δ and ε. This is not only essential to achieve tight bounds, but also sensible in practical situations, since it allows one to adapt the bound according to sample density and the amount of noise present in the sample separately.}, author = {Attali, Dominique and Kourimska, Hana and Fillmore, Christopher D and Ghosh, Ishika and Lieutier, André and Stephenson, Elizabeth R and Wintraecken, Mathijs}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, issn = {1868-8969}, location = {Athens, Greece}, pages = {11:1--11:19}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds}}, doi = {10.4230/LIPIcs.SoCG.2024.11}, volume = {293}, year = {2024}, }