@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 = {16113349}, 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}, } @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{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}, } @inproceedings{11428, abstract = {The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. 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. 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, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible.}, author = {Chambers, Erin and Fillmore, Christopher D and Stephenson, Elizabeth R and Wintraecken, Mathijs}, booktitle = {38th International Symposium on Computational Geometry}, editor = {Goaoc, Xavier and Kerber, Michael}, isbn = {978-3-95977-227-3}, issn = {1868-8969}, location = {Berlin, Germany}, pages = {66:1--66:9}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{A cautionary tale: Burning the medial axis is unstable}}, doi = {10.4230/LIPIcs.SoCG.2022.66}, volume = {224}, year = {2022}, } @inbook{11440, abstract = {To compute the persistent homology of a grayscale digital image one needs to build a simplicial or cubical complex from it. For cubical complexes, the two commonly used constructions (corresponding to direct and indirect digital adjacencies) can give different results for the same image. The two constructions are almost dual to each other, and we use this relationship to extend and modify the cubical complexes to become dual filtered cell complexes. We derive a general relationship between the persistent homology of two dual filtered cell complexes, and also establish how various modifications to a filtered complex change the persistence diagram. Applying these results to images, we derive a method to transform the persistence diagram computed using one type of cubical complex into a persistence diagram for the other construction. This means software for computing persistent homology from images can now be easily adapted to produce results for either of the two cubical complex constructions without additional low-level code implementation.}, author = {Bleile, Bea and Garin, Adélie and Heiss, Teresa and Maggs, Kelly and Robins, Vanessa}, booktitle = {Research in Computational Topology 2}, editor = {Gasparovic, Ellen and Robins, Vanessa and Turner, Katharine}, isbn = {9783030955182}, pages = {1--26}, publisher = {Springer Nature}, title = {{The persistent homology of dual digital image constructions}}, doi = {10.1007/978-3-030-95519-9_1}, volume = {30}, 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}, } @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{7791, abstract = {Extending a result of Milena Radnovic and Serge Tabachnikov, we establish conditionsfor two different non-symmetric norms to define the same billiard reflection law.}, author = {Akopyan, Arseniy and Karasev, Roman}, issn = {2199-6768}, journal = {European Journal of Mathematics}, number = {4}, pages = {1309 -- 1312}, publisher = {Springer Nature}, title = {{When different norms lead to same billiard trajectories?}}, doi = {10.1007/s40879-020-00405-0}, volume = {8}, year = {2022}, } @article{8338, abstract = {Canonical parametrisations of classical confocal coordinate systems are introduced and exploited to construct non-planar analogues of incircular (IC) nets on individual quadrics and systems of confocal quadrics. Intimate connections with classical deformations of quadrics that are isometric along asymptotic lines and circular cross-sections of quadrics are revealed. The existence of octahedral webs of surfaces of Blaschke type generated by asymptotic and characteristic lines that are diagonally related to lines of curvature is proved theoretically and established constructively. Appropriate samplings (grids) of these webs lead to three-dimensional extensions of non-planar IC nets. Three-dimensional octahedral grids composed of planes and spatially extending (checkerboard) IC-nets are shown to arise in connection with systems of confocal quadrics in Minkowski space. In this context, the Laguerre geometric notion of conical octahedral grids of planes is introduced. The latter generalise the octahedral grids derived from systems of confocal quadrics in Minkowski space. An explicit construction of conical octahedral grids is presented. The results are accompanied by various illustrations which are based on the explicit formulae provided by the theory.}, author = {Akopyan, Arseniy and Bobenko, Alexander I. and Schief, Wolfgang K. and Techter, Jan}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {938--976}, publisher = {Springer Nature}, title = {{On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs}}, doi = {10.1007/s00454-020-00240-w}, volume = {66}, 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}, } @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{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}, } @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}, } @inproceedings{9824, abstract = {We define a new compact coordinate system in which each integer triplet addresses a voxel in the BCC grid, and we investigate some of its properties. We propose a characterization of 3D discrete analytical planes with their topological features (in the Cartesian and in the new coordinate system) such as the interrelation between the thickness of the plane and the separability constraint we aim to obtain.}, author = {Čomić, Lidija and Zrour, Rita and Largeteau-Skapin, Gaëlle and Biswas, Ranita and Andres, Eric}, booktitle = {Discrete Geometry and Mathematical Morphology}, isbn = {9783030766566}, issn = {16113349}, location = {Uppsala, Sweden}, pages = {152--163}, publisher = {Springer Nature}, title = {{Body centered cubic grid - coordinate system and discrete analytical plane definition}}, doi = {10.1007/978-3-030-76657-3_10}, volume = {12708}, 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{8538, abstract = {We prove some recent experimental observations of Dan Reznik concerning periodic billiard orbits in ellipses. For example, the sum of cosines of the angles of a periodic billiard polygon remains constant in the 1-parameter family of such polygons (that exist due to the Poncelet porism). In our proofs, we use geometric and complex analytic methods.}, author = {Akopyan, Arseniy and Schwartz, Richard and Tabachnikov, Serge}, issn = {2199-6768}, journal = {European Journal of Mathematics}, publisher = {Springer Nature}, title = {{Billiards in ellipses revisited}}, doi = {10.1007/s40879-020-00426-9}, year = {2020}, } @inproceedings{8703, abstract = {Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity. }, author = {Osang, Georg F and Rouxel-Labbé, Mael and Teillaud, Monique}, booktitle = {28th Annual European Symposium on Algorithms}, isbn = {9783959771627}, issn = {18688969}, location = {Virtual, Online; Pisa, Italy}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Generalizing CGAL periodic Delaunay triangulations}}, doi = {10.4230/LIPIcs.ESA.2020.75}, volume = {173}, year = {2020}, }