@inproceedings{6648,
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},
booktitle = {35th International Symposium on Computational Geometry},
isbn = {9783959771047},
location = {Portland, OR, United States},
pages = {31:1--31:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Topological data analysis in information space}},
doi = {10.4230/LIPICS.SOCG.2019.31},
volume = {129},
year = {2019},
}
@article{6756,
abstract = {We study the topology generated by the temperature fluctuations of the cosmic microwave background (CMB) radiation, as quantified by the number of components and holes, formally given by the Betti numbers, in the growing excursion sets. We compare CMB maps observed by the Planck satellite with a thousand simulated maps generated according to the ΛCDM paradigm with Gaussian distributed fluctuations. The comparison is multi-scale, being performed on a sequence of degraded maps with mean pixel separation ranging from 0.05 to 7.33°. The survey of the CMB over 𝕊2 is incomplete due to obfuscation effects by bright point sources and other extended foreground objects like our own galaxy. To deal with such situations, where analysis in the presence of “masks” is of importance, we introduce the concept of relative homology. The parametric χ2-test shows differences between observations and simulations, yielding p-values at percent to less than permil levels roughly between 2 and 7°, with the difference in the number of components and holes peaking at more than 3σ sporadically at these scales. The highest observed deviation between the observations and simulations for b0 and b1 is approximately between 3σ and 4σ at scales of 3–7°. There are reports of mildly unusual behaviour of the Euler characteristic at 3.66° in the literature, computed from independent measurements of the CMB temperature fluctuations by Planck’s predecessor, the Wilkinson Microwave Anisotropy Probe (WMAP) satellite. The mildly anomalous behaviour of the Euler characteristic is phenomenologically related to the strongly anomalous behaviour of components and holes, or the zeroth and first Betti numbers, respectively. Further, since these topological descriptors show consistent anomalous behaviour over independent measurements of Planck and WMAP, instrumental and systematic errors may be an unlikely source. These are also the scales at which the observed maps exhibit low variance compared to the simulations, and approximately the range of scales at which the power spectrum exhibits a dip with respect to the theoretical model. Non-parametric tests show even stronger differences at almost all scales. Crucially, Gaussian simulations based on power-spectrum matching the characteristics of the observed dipped power spectrum are not able to resolve the anomaly. Understanding the origin of the anomalies in the CMB, whether cosmological in nature or arising due to late-time effects, is an extremely challenging task. Regardless, beyond the trivial possibility that this may still be a manifestation of an extreme Gaussian case, these observations, along with the super-horizon scales involved, may motivate the study of primordial non-Gaussianity. Alternative scenarios worth exploring may be models with non-trivial topology, including topological defect models.},
author = {Pranav, Pratyush and Adler, Robert J. and Buchert, Thomas and Edelsbrunner, Herbert and Jones, Bernard J.T. and Schwartzman, Armin and Wagner, Hubert and Van De Weygaert, Rien},
issn = {14320746},
journal = {Astronomy and Astrophysics},
publisher = {EDP Sciences},
title = {{Unexpected topology of the temperature fluctuations in the cosmic microwave background}},
doi = {10.1051/0004-6361/201834916},
volume = {627},
year = {2019},
}
@article{6608,
abstract = {We use the canonical bases produced by the tri-partition algorithm in (Edelsbrunner and Ölsböck, 2018) to open and close holes in a polyhedral complex, K. In a concrete application, we consider the Delaunay mosaic of a finite set, we let K be an Alpha complex, and we use the persistence diagram of the distance function to guide the hole opening and closing operations. The dependences between the holes define a partial order on the cells in K that characterizes what can and what cannot be constructed using the operations. The relations in this partial order reveal structural information about the underlying filtration of complexes beyond what is expressed by the persistence diagram.},
author = {Edelsbrunner, Herbert and Ölsböck, Katharina},
journal = {Computer Aided Geometric Design},
pages = {1--15},
publisher = {Elsevier},
title = {{Holes and dependences in an ordered complex}},
doi = {10.1016/j.cagd.2019.06.003},
volume = {73},
year = {2019},
}
@article{530,
abstract = {Inclusion–exclusion is an effective method for computing the volume of a union of measurable sets. We extend it to multiple coverings, proving short inclusion–exclusion formulas for the subset of Rn covered by at least k balls in a finite set. We implement two of the formulas in dimension n=3 and report on results obtained with our software.},
author = {Edelsbrunner, Herbert and Iglesias Ham, Mabel},
journal = {Computational Geometry: Theory and Applications},
pages = {119 -- 133},
publisher = {Elsevier},
title = {{Multiple covers with balls I: Inclusion–exclusion}},
doi = {10.1016/j.comgeo.2017.06.014},
volume = {68},
year = {2018},
}
@inproceedings{187,
abstract = {Given a locally finite X ⊆ ℝd and a radius r ≥ 0, the k-fold cover of X and r consists of all points in ℝd 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 ℝd+1 whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module from Delaunay mosaics that is isomorphic to the persistence module of the multi-covers. },
author = {Edelsbrunner, Herbert and Osang, Georg F},
location = {Budapest, Hungary},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{The multi-cover persistence of Euclidean balls}},
doi = {10.4230/LIPIcs.SoCG.2018.34},
volume = {99},
year = {2018},
}
@inproceedings{188,
abstract = {Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex.},
author = {Edelsbrunner, Herbert and Virk, Ziga and Wagner, Hubert},
location = {Budapest, Hungary},
pages = {35:1 -- 35:13},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Smallest enclosing spheres and Chernoff points in Bregman geometry}},
doi = {10.4230/LIPIcs.SoCG.2018.35},
volume = {99},
year = {2018},
}
@article{87,
abstract = {Using the geodesic distance on the n-dimensional sphere, we study the expected radius function of the Delaunay mosaic of a random set of points. Specifically, we consider the partition of the mosaic into intervals of the radius function and determine the expected number of intervals whose radii are less than or equal to a given threshold. We find that the expectations are essentially the same as for the Poisson–Delaunay mosaic in n-dimensional Euclidean space. Assuming the points are not contained in a hemisphere, the Delaunay mosaic is isomorphic to the boundary complex of the convex hull in Rn+1, so we also get the expected number of faces of a random inscribed polytope. As proved in Antonelli et al. [Adv. in Appl. Probab. 9–12 (1977–1980)], an orthant section of the n-sphere is isometric to the standard n-simplex equipped with the Fisher information metric. It follows that the latter space has similar stochastic properties as the n-dimensional Euclidean space. Our results are therefore relevant in information geometry and in population genetics.},
author = {Edelsbrunner, Herbert and Nikitenko, Anton},
journal = {Annals of Applied Probability},
number = {5},
pages = {3215 -- 3238},
publisher = {Institute of Mathematical Statistics},
title = {{Random inscribed polytopes have similar radius functions as Poisson-Delaunay mosaics}},
doi = {10.1214/18-AAP1389},
volume = {28},
year = {2018},
}
@article{312,
abstract = {Motivated by biological questions, we study configurations of equal spheres that neither pack nor cover. Placing their centers on a lattice, we define the soft density of the configuration by penalizing multiple overlaps. Considering the 1-parameter family of diagonally distorted 3-dimensional integer lattices, we show that the soft density is maximized at the FCC lattice.},
author = {Edelsbrunner, Herbert and Iglesias Ham, Mabel},
issn = {08954801},
journal = {SIAM J Discrete Math},
number = {1},
pages = {750 -- 782},
publisher = {Society for Industrial and Applied Mathematics },
title = {{On the optimality of the FCC lattice for soft sphere packing}},
doi = {10.1137/16M1097201},
volume = {32},
year = {2018},
}
@article{5678,
abstract = {The order-k Voronoi tessellation of a locally finite set 𝑋⊆ℝ𝑛 decomposes ℝ𝑛 into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold.},
author = {Edelsbrunner, Herbert and Nikitenko, Anton},
issn = {14320444},
journal = {Discrete and Computational Geometry},
publisher = {Springer},
title = {{Poisson–Delaunay Mosaics of Order k}},
doi = {10.1007/s00454-018-0049-2},
year = {2018},
}
@article{1022,
abstract = {We introduce a multiscale topological description of the Megaparsec web-like cosmic matter distribution. Betti numbers and topological persistence offer a powerful means of describing the rich connectivity structure of the cosmic web and of its multiscale arrangement of matter and galaxies. Emanating from algebraic topology and Morse theory, Betti numbers and persistence diagrams represent an extension and deepening of the cosmologically familiar topological genus measure and the related geometric Minkowski functionals. In addition to a description of the mathematical background, this study presents the computational procedure for computing Betti numbers and persistence diagrams for density field filtrations. The field may be computed starting from a discrete spatial distribution of galaxies or simulation particles. The main emphasis of this study concerns an extensive and systematic exploration of the imprint of different web-like morphologies and different levels of multiscale clustering in the corresponding computed Betti numbers and persistence diagrams. To this end, we use Voronoi clustering models as templates for a rich variety of web-like configurations and the fractal-like Soneira-Peebles models exemplify a range of multiscale configurations. We have identified the clear imprint of cluster nodes, filaments, walls, and voids in persistence diagrams, along with that of the nested hierarchy of structures in multiscale point distributions. We conclude by outlining the potential of persistent topology for understanding the connectivity structure of the cosmic web, in large simulations of cosmic structure formation and in the challenging context of the observed galaxy distribution in large galaxy surveys.},
author = {Pranav, Pratyush and Edelsbrunner, Herbert and Van De Weygaert, Rien and Vegter, Gert and Kerber, Michael and Jones, Bernard and Wintraecken, Mathijs},
issn = {00358711},
journal = {Monthly Notices of the Royal Astronomical Society},
number = {4},
pages = {4281 -- 4310},
publisher = {Oxford University Press},
title = {{The topology of the cosmic web in terms of persistent Betti numbers}},
doi = {10.1093/mnras/stw2862},
volume = {465},
year = {2017},
}
@article{1072,
abstract = {Given a finite set of points in Rn and a radius parameter, we study the Čech, Delaunay–Čech, Delaunay (or alpha), and Wrap complexes in the light of generalized discrete Morse theory. Establishing the Čech and Delaunay complexes as sublevel sets of generalized discrete Morse functions, we prove that the four complexes are simple-homotopy equivalent by a sequence of simplicial collapses, which are explicitly described by a single discrete gradient field.},
author = {Bauer, Ulrich and Edelsbrunner, Herbert},
journal = {Transactions of the American Mathematical Society},
number = {5},
pages = {3741 -- 3762},
publisher = {American Mathematical Society},
title = {{The Morse theory of Čech and delaunay complexes}},
volume = {369},
year = {2017},
}
@article{1173,
abstract = {We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions.},
author = {Edelsbrunner, Herbert and Glazyrin, Alexey and Musin, Oleg and Nikitenko, Anton},
issn = {02099683},
journal = {Combinatorica},
number = {5},
pages = {887 -- 910},
publisher = {Springer},
title = {{The Voronoi functional is maximized by the Delaunay triangulation in the plane}},
doi = {10.1007/s00493-016-3308-y},
volume = {37},
year = {2017},
}
@article{718,
abstract = {Mapping every simplex in the Delaunay mosaic of a discrete point set to the radius of the smallest empty circumsphere gives a generalized discrete Morse function. Choosing the points from a Poisson point process in ℝ n , we study the expected number of simplices in the Delaunay mosaic as well as the expected number of critical simplices and nonsingular intervals in the corresponding generalized discrete gradient. Observing connections with other probabilistic models, we obtain precise expressions for the expected numbers in low dimensions. In particular, we obtain the expected numbers of simplices in the Poisson–Delaunay mosaic in dimensions n ≤ 4.},
author = {Edelsbrunner, Herbert and Nikitenko, Anton and Reitzner, Matthias},
issn = {00018678},
journal = {Advances in Applied Probability},
number = {3},
pages = {745 -- 767},
publisher = {Cambridge University Press},
title = {{Expected sizes of poisson Delaunay mosaics and their discrete Morse functions}},
doi = {10.1017/apr.2017.20},
volume = {49},
year = {2017},
}
@unpublished{6288,
abstract = {The order-k Voronoi tessellation of a locally finite set X⊆ℝn decomposes ℝn into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold. },
author = {Edelsbrunner, Herbert and Nikitenko, Anton},
booktitle = {arXiv:1709.09380},
pages = {11},
title = {{Poisson-Delaunay mosaics of order k}},
year = {2017},
}
@inproceedings{688,
abstract = {We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback - Leibler divergence, which is commonly used for comparing text and images, and the Itakura - Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized čech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory. },
author = {Edelsbrunner, Herbert and Wagner, Hubert},
issn = {18688969},
location = {Brisbane, Australia},
pages = {391--3916},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Topological data analysis with Bregman divergences}},
doi = {10.4230/LIPIcs.SoCG.2017.39},
volume = {77},
year = {2017},
}
@inbook{84,
abstract = {The advent of high-throughput technologies and the concurrent advances in information sciences have led to a data revolution in biology. This revolution is most significant in molecular biology, with an increase in the number and scale of the “omics” projects over the last decade. Genomics projects, for example, have produced impressive advances in our knowledge of the information concealed into genomes, from the many genes that encode for the proteins that are responsible for most if not all cellular functions, to the noncoding regions that are now known to provide regulatory functions. Proteomics initiatives help to decipher the role of post-translation modifications on the protein structures and provide maps of protein-protein interactions, while functional genomics is the field that attempts to make use of the data produced by these projects to understand protein functions. The biggest challenge today is to assimilate the wealth of information provided by these initiatives into a conceptual framework that will help us decipher life. For example, the current views of the relationship between protein structure and function remain fragmented. We know of their sequences, more and more about their structures, we have information on their biological activities, but we have difficulties connecting this dotted line into an informed whole. We lack the experimental and computational tools for directly studying protein structure, function, and dynamics at the molecular and supra-molecular levels. In this chapter, we review some of the current developments in building the computational tools that are needed, focusing on the role that geometry and topology play in these efforts. One of our goals is to raise the general awareness about the importance of geometric methods in elucidating the mysterious foundations of our very existence. Another goal is the broadening of what we consider a geometric algorithm. There is plenty of valuable no-man’s-land between combinatorial and numerical algorithms, and it seems opportune to explore this land with a computational-geometric frame of mind.},
author = {Edelsbrunner, Herbert and Koehl, Patrice},
booktitle = {Handbook of Discrete and Computational Geometry, Third Edition},
editor = {Toth, Csaba and O'Rourke, Joseph and Goodman, Jacob},
pages = {1709 -- 1735},
publisher = {CRC Press},
title = {{Computational topology for structural molecular biology}},
doi = {10.1201/9781315119601},
year = {2017},
}
@article{1662,
abstract = {We introduce a modification of the classic notion of intrinsic volume using persistence moments of height functions. Evaluating the modified first intrinsic volume on digital approximations of a compact body with smoothly embedded boundary in Rn, we prove convergence to the first intrinsic volume of the body as the resolution of the approximation improves. We have weaker results for the other modified intrinsic volumes, proving they converge to the corresponding intrinsic volumes of the n-dimensional unit ball.},
author = {Edelsbrunner, Herbert and Pausinger, Florian},
journal = {Advances in Mathematics},
pages = {674 -- 703},
publisher = {Academic Press},
title = {{Approximation and convergence of the intrinsic volume}},
doi = {10.1016/j.aim.2015.10.004},
volume = {287},
year = {2016},
}
@article{1295,
abstract = {Voronoi diagrams and Delaunay triangulations have been extensively used to represent and compute geometric features of point configurations. We introduce a generalization to poset diagrams and poset complexes, which contain order-k and degree-k Voronoi diagrams and their duals as special cases. Extending a result of Aurenhammer from 1990, we show how to construct poset diagrams as weighted Voronoi diagrams of average balls.},
author = {Edelsbrunner, Herbert and Iglesias Ham, Mabel},
journal = {Electronic Notes in Discrete Mathematics},
pages = {169 -- 174},
publisher = {Elsevier},
title = {{Multiple covers with balls II: Weighted averages}},
doi = {10.1016/j.endm.2016.09.030},
volume = {54},
year = {2016},
}
@article{1289,
abstract = {Aiming at the automatic diagnosis of tumors using narrow band imaging (NBI) magnifying endoscopic (ME) images of the stomach, we combine methods from image processing, topology, geometry, and machine learning to classify patterns into three classes: oval, tubular and irregular. Training the algorithm on a small number of images of each type, we achieve a high rate of correct classifications. The analysis of the learning algorithm reveals that a handful of geometric and topological features are responsible for the overwhelming majority of decisions.},
author = {Dunaeva, Olga and Edelsbrunner, Herbert and Lukyanov, Anton and Machin, Michael and Malkova, Daria and Kuvaev, Roman and Kashin, Sergey},
journal = {Pattern Recognition Letters},
number = {1},
pages = {13 -- 22},
publisher = {Elsevier},
title = {{The classification of endoscopy images with persistent homology}},
doi = {10.1016/j.patrec.2015.12.012},
volume = {83},
year = {2016},
}
@inproceedings{1495,
abstract = {Motivated by biological questions, we study configurations of equal-sized disks in the Euclidean plane that neither pack nor cover. Measuring the quality by the probability that a random point lies in exactly one disk, we show that the regular hexagonal grid gives the maximum among lattice configurations. },
author = {Edelsbrunner, Herbert and Iglesias Ham, Mabel and Kurlin, Vitaliy},
booktitle = {Proceedings of the 27th Canadian Conference on Computational Geometry},
location = {Ontario, Canada},
pages = {128--135},
publisher = {Queen's University},
title = {{Relaxed disk packing}},
volume = {2015-August},
year = {2015},
}