@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}, } @unpublished{15091, abstract = {Motivated by applications in the 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}, booktitle = {arXiv}, title = {{Chromatic alpha complexes}}, year = {2024}, } @article{12086, abstract = {We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-k mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-k mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order α-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.}, author = {Edelsbrunner, Herbert and Osang, Georg F}, issn = {1432-0541}, journal = {Algorithmica}, pages = {277--295}, publisher = {Springer Nature}, title = {{A simple algorithm for higher-order Delaunay mosaics and alpha shapes}}, doi = {10.1007/s00453-022-01027-6}, volume = {85}, year = {2023}, } @article{12544, abstract = {Geometry is crucial in our efforts to comprehend the structures and dynamics of biomolecules. For example, volume, surface area, and integrated mean and Gaussian curvature of the union of balls representing a molecule are used to quantify its interactions with the water surrounding it in the morphometric implicit solvent models. The Alpha Shape theory provides an accurate and reliable method for computing these geometric measures. In this paper, we derive homogeneous formulas for the expressions of these measures and their derivatives with respect to the atomic coordinates, and we provide algorithms that implement them into a new software package, AlphaMol. The only variables in these formulas are the interatomic distances, making them insensitive to translations and rotations. AlphaMol includes a sequential algorithm and a parallel algorithm. In the parallel version, we partition the atoms of the molecule of interest into 3D rectangular blocks, using a kd-tree algorithm. We then apply the sequential algorithm of AlphaMol to each block, augmented by a buffer zone to account for atoms whose ball representations may partially cover the block. The current parallel version of AlphaMol leads to a 20-fold speed-up compared to an independent serial implementation when using 32 processors. For instance, it takes 31 s to compute the geometric measures and derivatives of each atom in a viral capsid with more than 26 million atoms on 32 Intel processors running at 2.7 GHz. The presence of the buffer zones, however, leads to redundant computations, which ultimately limit the impact of using multiple processors. AlphaMol is available as an OpenSource software.}, author = {Koehl, Patrice and Akopyan, Arseniy and Edelsbrunner, Herbert}, issn = {1549-960X}, journal = {Journal of Chemical Information and Modeling}, number = {3}, pages = {973--985}, publisher = {American Chemical Society}, title = {{Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives}}, doi = {10.1021/acs.jcim.2c01346}, volume = {63}, year = {2023}, } @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}, publisher = {Springer Nature}, title = {{On angles in higher order Brillouin tessellations and related tilings in the plane}}, doi = {10.1007/s00454-023-00566-1}, year = {2023}, } @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}, publisher = {Springer Nature}, title = {{Geometric characterization of the persistence of 1D maps}}, doi = {10.1007/s41468-023-00126-9}, year = {2023}, } @article{10773, abstract = {The Voronoi tessellation in Rd is defined by locally minimizing the power distance to given weighted points. Symmetrically, the Delaunay mosaic can be defined by locally maximizing the negative power distance to other such points. We prove that the average of the two piecewise quadratic functions is piecewise linear, and that all three functions have the same critical points and values. Discretizing the two piecewise quadratic functions, we get the alpha shapes as sublevel sets of the discrete function on the Delaunay mosaic, and analogous shapes as superlevel sets of the discrete function on the Voronoi tessellation. For the same non-critical value, the corresponding shapes are disjoint, separated by a narrow channel that contains no critical points but the entire level set of the piecewise linear function.}, author = {Biswas, Ranita and Cultrera Di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {811--842}, publisher = {Springer Nature}, title = {{Continuous and discrete radius functions on Voronoi tessellations and Delaunay mosaics}}, doi = {10.1007/s00454-022-00371-2}, volume = {67}, year = {2022}, } @article{11660, 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 collections of interrelated sorted lists together with their persistence diagrams. }, author = {Biswas, Ranita and Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza}, journal = {LIPIcs}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{A window to the persistence of 1D maps. I: Geometric characterization of critical point pairs}}, year = {2022}, } @article{11658, 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}, journal = {Leibniz International Proceedings on Mathematics}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{Depth in arrangements: Dehn–Sommerville–Euler relations with applications}}, year = {2022}, } @unpublished{15090, 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}, booktitle = {arXiv}, title = {{On the size of chromatic Delaunay mosaics}}, year = {2022}, } @article{9465, abstract = {Given a locally finite set 𝑋⊆ℝ𝑑 and an integer 𝑘≥0, we consider the function 𝐰𝑘:Del𝑘(𝑋)→ℝ on the dual of the order-k Voronoi tessellation, whose sublevel sets generalize the notion of alpha shapes from order-1 to order-k (Edelsbrunner et al. in IEEE Trans Inf Theory IT-29:551–559, 1983; Krasnoshchekov and Polishchuk in Inf Process Lett 114:76–83, 2014). While this function is not necessarily generalized discrete Morse, in the sense of Forman (Adv Math 134:90–145, 1998) and Freij (Discrete Math 309:3821–3829, 2009), we prove that it satisfies similar properties so that its increments can be meaningfully classified into critical and non-critical steps. This result extends to the case of weighted points and sheds light on k-fold covers with balls in Euclidean space.}, author = {Edelsbrunner, Herbert and Nikitenko, Anton and Osang, Georg F}, issn = {14208997}, journal = {Journal of Geometry}, number = {1}, publisher = {Springer Nature}, title = {{A step in the Delaunay mosaic of order k}}, doi = {10.1007/s00022-021-00577-4}, volume = {112}, year = {2021}, } @inproceedings{9345, abstract = {Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction.}, author = {Edelsbrunner, Herbert and Heiss, Teresa and Kurlin , Vitaliy and Smith, Philip and Wintraecken, Mathijs}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, issn = {1868-8969}, location = {Virtual}, pages = {32:1--32:16}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The density fingerprint of a periodic point set}}, doi = {10.4230/LIPIcs.SoCG.2021.32}, volume = {189}, year = {2021}, } @inproceedings{9604, abstract = {Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation.}, author = {Biswas, Ranita and Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza}, booktitle = {Leibniz International Proceedings in Informatics}, isbn = {9783959771849}, issn = {18688969}, location = {Online}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Counting cells of order-k voronoi tessellations in ℝ3 with morse theory}}, doi = {10.4230/LIPIcs.SoCG.2021.16}, volume = {189}, year = {2021}, } @article{9317, abstract = {Given a locally finite X⊆Rd and a radius r≥0, the k-fold cover of X and r consists of all points in Rd that have k or more points of X within distance r. We consider two filtrations—one in scale obtained by fixing k and increasing r, and the other in depth obtained by fixing r and decreasing k—and we compute the persistence diagrams of both. While standard methods suffice for the filtration in scale, we need novel geometric and topological concepts for the filtration in depth. In particular, we introduce a rhomboid tiling in Rd+1 whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module of Delaunay mosaics that is isomorphic to the persistence module of the multi-covers.}, author = {Edelsbrunner, Herbert and Osang, Georg F}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {1296–1313}, publisher = {Springer Nature}, title = {{The multi-cover persistence of Euclidean balls}}, doi = {10.1007/s00454-021-00281-9}, volume = {65}, year = {2021}, } @article{10222, abstract = {Consider a random set of points on the unit sphere in ℝd, which can be either uniformly sampled or a Poisson point process. Its convex hull is a random inscribed polytope, whose boundary approximates the sphere. We focus on the case d = 3, for which there are elementary proofs and fascinating formulas for metric properties. In particular, we study the fraction of acute facets, the expected intrinsic volumes, the total edge length, and the distance to a fixed point. Finally we generalize the results to the ellipsoid with homeoid density.}, author = {Akopyan, Arseniy and Edelsbrunner, Herbert and Nikitenko, Anton}, issn = {1944-950X}, journal = {Experimental Mathematics}, pages = {1--15}, publisher = {Taylor and Francis}, title = {{The beauty of random polytopes inscribed in the 2-sphere}}, doi = {10.1080/10586458.2021.1980459}, year = {2021}, } @article{10204, abstract = {Two common representations of close packings of identical spheres consisting of hexagonal layers, called Barlow stackings, appear abundantly in minerals and metals. These motifs, however, occupy an identical portion of space and bear identical first-order topological signatures as measured by persistent homology. Here we present a novel method based on k-fold covers that unambiguously distinguishes between these patterns. Moreover, our approach provides topological evidence that the FCC motif is the more stable of the two in the context of evolving experimental sphere packings during the transition from disordered to an ordered state. We conclude that our approach can be generalised to distinguish between various Barlow stackings manifested in minerals and metals.}, author = {Osang, Georg F and Edelsbrunner, Herbert and Saadatfar, Mohammad}, issn = {1744-6848}, journal = {Soft Matter}, number = {40}, pages = {9107--9115}, publisher = {Royal Society of Chemistry }, title = {{Topological signatures and stability of hexagonal close packing and Barlow stackings}}, doi = {10.1039/d1sm00774b}, volume = {17}, year = {2021}, } @inproceedings{8135, abstract = {Discrete Morse theory has recently lead to new developments in the theory of random geometric complexes. This article surveys the methods and results obtained with this new approach, and discusses some of its shortcomings. It uses 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 = {Edelsbrunner, Herbert and Nikitenko, Anton and Ölsböck, Katharina and Synak, Peter}, booktitle = {Topological Data Analysis}, isbn = {9783030434076}, issn = {21978549}, pages = {181--218}, publisher = {Springer Nature}, title = {{Radius functions on Poisson–Delaunay mosaics and related complexes experimentally}}, doi = {10.1007/978-3-030-43408-3_8}, volume = {15}, year = {2020}, } @article{9630, abstract = {Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context.}, author = {Edelsbrunner, Herbert and Virk, Ziga and Wagner, Hubert}, issn = {1920180X}, journal = {Journal of Computational Geometry}, number = {2}, pages = {162--182}, publisher = {Carleton University}, title = {{Topological data analysis in information space}}, doi = {10.20382/jocg.v11i2a7}, volume = {11}, year = {2020}, } @article{7554, abstract = {Slicing a Voronoi tessellation in ${R}^n$ with a $k$-plane gives a $k$-dimensional weighted Voronoi tessellation, also known as a power diagram or Laguerre tessellation. Mapping every simplex of the dual weighted Delaunay mosaic to the radius of the smallest empty circumscribed sphere whose center lies in the $k$-plane gives a generalized discrete Morse function. Assuming the Voronoi tessellation is generated by a Poisson point process in ${R}^n$, we study the expected number of simplices in the $k$-dimensional weighted Delaunay mosaic as well as the expected number of intervals of the Morse function, both as functions of a radius threshold. As a by-product, we obtain a new proof for the expected number of connected components (clumps) in a line section of a circular Boolean model in ${R}^n$.}, author = {Edelsbrunner, Herbert and Nikitenko, Anton}, issn = {10957219}, journal = {Theory of Probability and its Applications}, number = {4}, pages = {595--614}, publisher = {SIAM}, title = {{Weighted Poisson–Delaunay mosaics}}, doi = {10.1137/S0040585X97T989726}, volume = {64}, year = {2020}, } @article{7666, abstract = {Generalizing the decomposition of a connected planar graph into a tree and a dual tree, we prove a combinatorial analog of the classic Helmholtz–Hodge decomposition of a smooth vector field. Specifically, we show that for every polyhedral complex, K, and every dimension, p, there is a partition of the set of p-cells into a maximal p-tree, a maximal p-cotree, and a collection of p-cells whose cardinality is the p-th reduced Betti number of K. Given an ordering of the p-cells, this tri-partition is unique, and it can be computed by a matrix reduction algorithm that also constructs canonical bases of cycle and boundary groups.}, author = {Edelsbrunner, Herbert and Ölsböck, Katharina}, issn = {14320444}, journal = {Discrete and Computational Geometry}, pages = {759--775}, publisher = {Springer Nature}, title = {{Tri-partitions and bases of an ordered complex}}, doi = {10.1007/s00454-020-00188-x}, volume = {64}, year = {2020}, }