3,482 research outputs found
LIPIcs
Full text linkThe 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². In particular, there is an arrangement of n contruent balls in ℝ³ that enclose a quadratic number of voids, which answers a long-standing open question in computational geometry
Topological Data Analysis with Bregman Divergences
Full text linkWe 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 Cech 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 Cech, 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
On Spheres with k Points Inside
Full text linkWe 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
Smallest Enclosing Spheres and Chernoff Points in BregmanGeometry
Full text linkSmallest 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
The Multi-cover Persistence of Euclidean Balls
Full text linkGiven a locally finite X subseteq R^d and a radius r >= 0, the k-fold cover of X and r consists of all points in R^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 R^{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
Topological Data Analysis in Information Space
Full text linkVarious 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
Banana Trees for the Persistence in Time Series Experimentally
Full text linkIn 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
Modes of Gaussian Mixtures and an Inequality for the Distance Between Curves in Space
No full textThis dissertation studiess high dimensional problems from a low dimensional perspective. First, we explore rectifiable curves in high-dimensional space by using the Fréchet distance between and total curvatures of the two curves to bound the difference of their lengths. We create this bound by mapping the curves into R^2 while preserving the length between the curves and increasing neitherthe total curvature of the curves nor the Fr\'echet distance between them. The bound is independent of the dimension of the ambient Euclidean space, it improves upon a bound by Cohen-Steiner and Edelsbrunner for dimensions greater than three and it generalizesa result by F\'ary and Chakerian.In the second half of the dissertation, we analyze Gaussian mixtures. In particular, we consider the sum of n Gaussians, where each Gaussian is centered at the vertex of a regular n-simplex. Fixing the width of the Guassians and varying the diameter of the simplex from zero to infinity by increasing a parameter that we call the scale factor, we find the window of scale factors for which the Gaussian mixture has more modes, or local maxima, than components of the mixture.We see that the extra mode created is subtle, but can be higher than the modes closer to the vertices of the simplex. In addition, we prove that all critical points are located on a set of one-dimensional lines (axes) connecting barycenters of complementary faces ofthe simplex.</p
Letter from Herbert Nicholson to Michi Weglyn, October 30, 1980
No full textA letter from Herbert Nicholson to Michi Weglyn about his experiences working with other religious figures in the Manzanar incarceration camp.These materials are from box 73 and 74 of the Frank Chin Papers. The Frank Chin Papers contain personal and professional correspondence between Frank Chin and Michi Weglyn relating to particular projects on which either author was working as well as files related to the Day of Remembrance Tribute to Michi Weglyn
- …
