@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{20980,
abstract = {Morse decompositions partition the flows in a vector field into equivalent structures. Given such a decomposition, one can define a further summary of its flow structure by what is called a connection matrix. These matrices, a generalization of Morse boundary operators from classical Morse theory, capture the connections made by the flows among the critical structures—such as attractors, repellers, and orbits—in a vector field. Recently, in the context of combinatorial dynamics, an efficient persistence-like algorithm to compute connection matrices has been proposed in Dey, Lipiński, Mrozek, and Slechta [SIAM J. Appl. Dyn. Syst., 23 (2024), pp. 81–97]. We show that, actually, the classical persistence algorithm with exhaustive reduction retrieves connection matrices, both simplifying the algorithm of Dey et al. and bringing the theory of persistence closer to combinatorial dynamical systems. We supplement this main result with an observation: the concept of persistence as defined for scalar fields naturally adapts to Morse decompositions whose Morse sets are filtered with a Lyapunov function. We conclude by presenting preliminary experimental results.},
author = {Dey, Tamal K. and Haas, Andrew and Lipiński, Michał},
issn = {1536-0040},
journal = {SIAM Journal on Applied Dynamical Systems},
number = {1},
pages = {108--130},
publisher = {Society for Industrial & Applied Mathematics},
title = {{Computing a connection matrix and persistence efficiently from a morse decomposition}},
doi = {10.1137/25m1739406},
volume = {25},
year = {2026},
}
@inbook{21056,
abstract = {In this work, we introduce and study what we believe is an intriguing, and, to the best of our knowledge, previously unknown connection between two fundamental areas in computational topology, namely topological data analysis (TDA) and knot theory. Given a function from a topological space to ℝ, TDA provides tools to simplify and study the importance of topological features: in particular, the 𝑙^𝑡ℎ-dimensional persistence diagram encodes the topological changes (or 𝑙-homology) in the sublevel set as the function value increases into a set of points in the plane. Given a continuous one parameter family of such functions, we can combine the persistence diagrams into an object known as a vineyard, which tracks the evolution of points in the persistence diagram as the function changes. If we further restrict that family of functions to be periodic, we identify the two ends of the vineyard, yielding a closed vineyard. This allows the study of monodromy, which in this context means that following the family of functions for a period permutes the set of points in a non-trivial way. Recent work has studied monodromy in the directional persistent homology transform, demonstrating some interesting connections between an input shape and monodromy in the persistent homology transform for 0-dimensional homology embedded in ℝ^2.
In this work, given a link and a value 𝑙, we construct a topological space (based on the given link) and periodic family of functions on this space (based on the Euclidean distance function), such that the closed 𝑙-vineyard contains this link. This shows that vineyards are topologically as rich as one could possibly hope, suggesting many future directions of work. Importantly, it has at least two immediate consequences we explicitly point out:
1. Monodromy of any periodicity can occur in a 𝑙-vineyard for any 𝑙. This answers a variant of a question by Arya and collaborators. To exhibit this as a consequence of our first main result we also reformulate monodromy in a more geometric way, which may be of interest in itself.
2. Topologically distinguishing closed vineyards is likely to be difficult (from a complexity theory as well as from a practical perspective) because of the difficulty of knot and link recognition, which have strong connections to many NP-hard problems.},
author = {Chambers, Erin W. and Fillmore, Christopher D and Stephenson, Elizabeth R and Wintraecken, Mathijs},
booktitle = {Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms},
editor = {Green Larsen, Kasper and Saha, Barna},
pages = {6240--6263},
publisher = {Society for Industrial and Applied Mathematics},
title = {{Braiding Vineyards}},
doi = {10.1137/1.9781611978971.225},
year = {2026},
}
@article{21115,
abstract = {Quantifying cell morphology is central to understanding cellular regulation, fate, and heterogeneity, yet conventional image-based analyses often struggle with diverse or irregular shapes. We present a computational framework that uses topological data analysis to characterise and compare single-cell morphologies from fluorescence microscopy. Each cell is represented by its contour together with the position of its nucleus, from which we construct a filtration based on a radial distance function and derive a persistence diagram encoding the shape’s topological evolution. The similarity between two cells is quantified using the 2-Wasserstein distance between their diagrams, yielding a shape distance we call the PH distance. We apply this method to two representative experimental systems—primary human mesenchymal stem cells (hMSCs) and HeLa cells—and show that PH distances enable the detection of outliers in those systems, the identification of sub-populations, and the quantification of shape heterogeneity. We benchmark PH against three established contour-based distances (aspect ratio, Fourier descriptors, and elastic shape analysis) and show that PH offers better separation between cell types and greater robustness when clustering heterogeneous populations. Together, these results demonstrate that persistent-homology-based signatures provide a principled and sensitive approach for analysing cell morphology in settings where traditional geometric or image-based descriptors are insufficient.},
author = {Bleile, Yossi and Yadav, Pooja and Koehl, Patrice and Rehfeldt, Florian},
issn = {1553-7358},
journal = {PLoS Computational Biology},
publisher = {Public Library of Science},
title = {{Persistence diagrams as morphological signatures of cells: A method to measure and compare cells within a population}},
doi = {10.1371/journal.pcbi.1013890},
volume = {22},
year = {2026},
}
@article{21232,
abstract = {Abstract
In this paper, we consider a simple class of stratified spaces – 2-complexes. We present an algorithm that learns the abstract structure of an embedded 2-complex from a point cloud sampled from it. We use tools and inspiration from computational geometry, algebraic topology, and topological data analysis and prove the correctness of the identified abstract structure under assumptions on the embedding.},
author = {Bleile, Yossi},
issn = {2730-9657},
journal = {La Matematica},
publisher = {Springer Nature},
title = {{Towards stratified space learning: 2-complexes}},
doi = {10.1007/s44007-025-00183-9},
volume = {5},
year = {2026},
}
@inproceedings{21374,
abstract = {Let . S be a set of distinct points in general position in the
Euclidean plane. A plane Hamiltonian path on . S is a crossing-free geometric path such that every point of .S is a vertex of the path. It is
known that, if. S is sufficiently large, there exist three edge-disjoint plane
Hamiltonian paths on . S. In this paper we study an edge-constrained
version of the problem of finding Hamiltonian paths on a point set. We
first consider the problem of finding a single plane Hamiltonian path . π
with endpoints .s, t ∈ S and constraints given by a segment . ab, where
.a, b ∈ S. We consider the following scenarios: (i) .ab ∈ π; (ii) .ab π. We
characterize those quintuples . S, a, b, s, t for which . π exists. Secondly,
we consider the problem of finding two plane Hamiltonian paths . π1, π2
on a set . S with constraints given by a segment . ab, where .a, b ∈ S. We
consider the following scenarios: (i) .π1 and .π2 share no edges and .ab is
an edge of . π1; (ii) .π1 and .π2 share no edges and none of them includes
.ab as an edge; (iii) both .π1 and .π2 include .ab as an edge and share no
other edges. In all cases, we characterize those triples . S, a, b for which
.π1 and .π2 exist.},
author = {Antić, Todor and Džuklevski, Aleksa and Fiala, Jiří and Kratochvíl, Jan and Liotta, Giuseppe and Saghafian, Morteza and Saumell, Maria and Zink, Johannes},
booktitle = {51st International Conference on Current Trends in Theory and Practice of Computer Science},
isbn = {9783032178008},
issn = {1611-3349},
location = {Krakow, Poland},
pages = {532--546},
publisher = {Springer Nature},
title = {{Edge-constrained Hamiltonian paths on a point set}},
doi = {10.1007/978-3-032-17801-5_39},
volume = {16448},
year = {2026},
}
@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},
}
@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},
}
@phdthesis{21021,
abstract = {This thesis examines how geometry and topology intersect in the representation, transformation, and analysis of complex shapes. It considers how continuous manifolds relate to their discrete analogues, how topological structures evolve in persistence vineyards, and how tools from topological data analysis can illuminate problems in mathematical physics. Central to this exploration is the question of how structure, both geometric and topological, persists or changes under approximation, sampling, or deformation. The work develops new approaches to skeletal and grid-based representations of surfaces, reveals the full expressive capacity of persistence vineyards, and applies topological methods to the longstanding problem of equilibria in electrostatic fields. These threads braid together into a broader understanding of how topology and geometry inform one another across theory, computation, and application.},
author = {Fillmore, Christopher D},
issn = {2663-337X},
pages = {122},
publisher = {Institute of Science and Technology Austria},
title = {{Braiding geometry and topology to study shapes and data}},
doi = {10.15479/AT-ISTA-21021},
year = {2026},
}
@unpublished{21051,
abstract = {In this work, we introduce and study what we believe is an intriguing and, to the best of our knowledge, previously unknown connection between two areas in computational topology, topological data analysis (TDA) and knot theory. Given a function from a topological space to $\mathbb{R}$, TDA provides tools to simplify and study the importance of topological features: in particular, the $l^{th}$-dimensional persistence diagram encodes the $l$-homology in the sublevel set as the function value increases as a set of points in the plane. Given a continuous one-parameter family of such functions, we can combine the persistence diagrams into an object known as a vineyard, which track the evolution of points in the persistence diagram. If we further restrict that family of functions to be periodic, we identify the two ends of the vineyard, yielding a closed vineyard. This allows the study of monodromy, which in this context means that following the family of functions for a period permutes the set of points in a non-trivial way. In this work, given a link and value $l$, we construct a topological space and periodic family of functions such that the closed $l$-vineyard contains this link. This shows that vineyards are topologically as rich as one could possibly hope. Importantly, it has at least two immediate consequences: First, monodromy of any periodicity can occur in a $l$-vineyard, answering a variant of a question by [Arya et al 2024]. To exhibit this, we also reformulate monodromy in a more geometric way, which may be of interest in itself. Second, distinguishing vineyards is likely to be difficult given the known difficulty of knot and link recognition, which have strong connections to many NP-hard problems.},
author = { Chambers, Erin and Fillmore, Christopher D and Stephenson, Elizabeth R and Wintraecken, Mathijs},
booktitle = {arXiv},
title = {{Braiding vineyards}},
doi = {10.48550/ARXIV.2504.11203},
year = {2026},
}
@article{21781,
abstract = {Given a set A of n points (vertices) in general position in the plane, the complete geometric graph
Kn[A] consists of all (n2) segments (edges) between the elements of A. It is known that the edge set of every complete geometric graph on n vertices can be partitioned into O(n3∕2) crossing-free paths (or matchings). We strengthen this result under various additional assumptions on the point set. In particular, we prove that for a set A of n randomly selected points, uniformly distributed in [0,1]2, with probability tending to 1 as n→∞, the edge set of Kn[A] can be covered by O(nlogn) crossing-free paths and by O(n√logn) crossing-free matchings. On the other hand, we construct n-element point sets such that covering the edge set of Kn[A] requires a quadratic number of monotone paths.},
author = {Dumitrescu, Adrian and Pach, János and Saghafian, Morteza and Scott, Alex},
issn = {2996-220X},
journal = {Combinatorics and Number Theory},
number = {1},
pages = {73--82},
publisher = {Mathematical Sciences Publishers},
title = {{Covering complete geometric graphs by monotone paths}},
doi = {10.2140/cnt.2026.15.73},
volume = {15},
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},
}
@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},
}
@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},
}