@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}, } @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}, } @inproceedings{20729, abstract = {Persistence modules (defined as a sequence of vector spaces and linear maps between them) are a key tool in topological data analysis. They are easy to interpret and fast to compute. However, when considering persistence maps (i.e. maps between persistence modules), these properties are lost. We propose a new invariant for persistence maps consisting of a partial matching such that: it is easy to interpret, it is more discriminative than the image of the persistence map, and can be calculated with cubical complexity.}, author = {Gonzalez-Diaz, Rocio and Soriano Trigueros, Manuel and Torras-Casas, Alvaro}, booktitle = {Proceedings of the 2025 International Symposium on Symbolic and Algebraic Computation}, isbn = {9798400720758}, location = {Guanajuato, Mexico}, pages = {188--196}, publisher = {Association for Computing Machinery}, title = {{Additive partial matchings for persistent homology}}, doi = {10.1145/3747199.3747561}, 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}, } @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{13182, abstract = {We characterize critical points of 1-dimensional maps paired in persistent homology geometrically and this way get elementary proofs of theorems about the symmetry of persistence diagrams and the variation of such maps. In particular, we identify branching points and endpoints of networks as the sole source of asymmetry and relate the cycle basis in persistent homology with a version of the stable marriage problem. Our analysis provides the foundations of fast algorithms for maintaining a collection of sorted lists together with its persistence diagram.}, 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 = {1101--1119}, publisher = {Springer Nature}, title = {{Geometric characterization of the persistence of 1D maps}}, doi = {10.1007/s41468-023-00126-9}, volume = {8}, 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{14888, abstract = {A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces.}, author = {De Nooijer, Phoebe and Terziadis, Soeren and Weinberger, Alexandra and Masárová, Zuzana and Mchedlidze, Tamara and Löffler, Maarten and Rote, Günter}, booktitle = {31st International Symposium on Graph Drawing and Network Visualization}, isbn = {9783031492747}, issn = {1611-3349}, location = {Isola delle Femmine, Palermo, Italy}, pages = {18--33}, publisher = {Springer Nature}, title = {{Removing popular faces in curve arrangements}}, doi = {10.1007/978-3-031-49275-4_2}, volume = {14466}, year = {2024}, } @inproceedings{15012, abstract = {We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on n vertices cannot be decomposed into fewer than n-1 star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs.}, author = {Pach, János and Saghafian, Morteza and Schnider, Patrick}, booktitle = {31st International Symposium on Graph Drawing and Network Visualization}, isbn = {9783031492716}, issn = {1611-3349}, location = {Isola delle Femmine, Palermo, Italy}, pages = {339--346}, publisher = {Springer Nature}, title = {{Decomposition of geometric graphs into star-forests}}, doi = {10.1007/978-3-031-49272-3_23}, volume = {14465}, year = {2024}, } @inproceedings{15093, abstract = {We present a dynamic data structure for maintaining the persistent homology of a time series of real numbers. The data structure supports local operations, including the insertion and deletion of an item and the cutting and concatenating of lists, each in time O(log n + k), in which n counts the critical items and k the changes in the augmented persistence diagram. To achieve this, we design a tailor-made tree structure with an unconventional representation, referred to as banana tree, which may be useful in its own right.}, author = {Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert and Henzinger, Monika H and Ost, Lara}, booktitle = {Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, editor = {Woodruff, David P.}, location = {Alexandria, VA, USA}, pages = {243 -- 295}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Dynamically maintaining the persistent homology of time series}}, doi = {10.1137/1.9781611977912.11}, year = {2024}, } @phdthesis{15094, abstract = {Point sets, geometric networks, and arrangements of hyperplanes are fundamental objects in discrete geometry that have captivated mathematicians for centuries, if not millennia. This thesis seeks to cast new light on these structures by illustrating specific instances where a topological perspective, specifically through discrete Morse theory and persistent homology, provides valuable insights. At first glance, the topology of these geometric objects might seem uneventful: point sets essentially lack of topology, arrangements of hyperplanes are a decomposition of Rd, which is a contractible space, and the topology of a network primarily involves the enumeration of connected components and cycles within the network. However, beneath this apparent simplicity, there lies an array of intriguing structures, a small subset of which will be uncovered in this thesis. Focused on three case studies, each addressing one of the mentioned objects, this work will showcase connections that intertwine topology with diverse fields such as combinatorial geometry, algorithms and data structures, and emerging applications like spatial biology. }, author = {Cultrera di Montesano, Sebastiano}, issn = {2663-337X}, pages = {108}, publisher = {Institute of Science and Technology Austria}, title = {{Persistence and Morse theory for discrete geometric structures}}, doi = {10.15479/at:ista:15094}, year = {2024}, } @article{15247, abstract = {Extending the notion of sunflowers, we call a family of at least two sets an odd-sunflower if every element of the underlying set is contained in an odd number of sets or in none of them. It follows from the Erdős–Szemerédi conjecture, recently proved by Naslund and Sawin, that there is a constant <2 such that every family of subsets of an n-element set that contains no odd-sunflower consists of at most n sets. We construct such families of size at least 1.5021n. We also characterize minimal odd-sunflowers of triples.}, author = {Frankl, Peter and Pach, János and Pálvölgyi, Dömötör}, issn = {1096-0899}, journal = {Journal of Combinatorial Theory, Series A}, number = {8}, publisher = {Elsevier}, title = {{Odd-sunflowers}}, doi = {10.1016/j.jcta.2024.105889}, volume = {206}, 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{17145, abstract = {Grid peeling is the process of repeatedly removing the convex hull vertices of the grid points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the affine curve-shortening flow, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes.}, author = {Rote, Günter and Rüber, Moritz and Saghafian, Morteza}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, issn = {1868-8969}, location = {Athens, Greece}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Grid peeling of parabolas}}, doi = {10.4230/LIPIcs.SoCG.2024.76}, 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}, } @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}, } @article{18604, abstract = {A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a randomized FPT-time algorithm where the parameter is the number of popular faces.}, author = {De Nooijer, Phoebe and Terziadis, Soeren and Weinberger, Alexandra and Masárová, Zuzana and Mchedlidze, Tamara and Löffler, Maarten and Rote, Günter}, issn = {1526-1719}, journal = {Journal of Graph Algorithms and Applications}, number = {2}, pages = {47--82}, publisher = {Brown University}, title = {{Removing popular faces in curve arrangements}}, doi = {10.7155/jgaa.v28i2.2988}, volume = {28}, year = {2024}, }