The weighted Euler characteristic transform (WECT) is a new tool for extracting shape information from data equipped with a weight function. Image data may benefit from the WECT where the intensity of the pixels are used to define the weight function. In this work, an empirical assessment of the WECT's ability to distinguish shapes on images with different pixel intensity distributions is considered, along with visualization techniques to improve the intuition and understanding of what is captured by the WECT. Additionally, the expected weighted Euler characteristic and the expected WECT are derived.

The persistent homology transform, Betti function transform, and Euler characteristic transform represent a shape with a multiset of persistence diagrams, Betti functions, or Euler characteristic functions, respectively, parameterized by the sphere of directions in the ambient space. In this work, we give the first explicit construction of finite sets of directions discretizing the verbose variants of these transforms and show that such discretizations faithfully represent the underlying shape. Our discretization, while exponential in the dimension of the shape, does not depend on any restrictions on the particular immersion beyond general position, and is stable with respect to various perturbations.

Merge trees are a valuable tool in the scientific visualization of scalar fields; however, current methods for merge tree comparisons are computationally expensive, primarily due to the exhaustive matching between tree nodes. To address this challenge, we introduce the Merge Tree Neural Network (MTNN), a learned neural network model designed for merge tree comparison. The MTNN enables rapid and high-quality similarity computation. We first demonstrate how to train graph neural networks, which emerged as effective encoders for graphs, in order to produce embeddings of merge trees in vector spaces for efficient similarity comparison. Next, we formulate the novel MTNN model that further improves the similarity comparisons by integrating the tree and node embeddings with a new topological attention mechanism. We demonstrate the effectiveness of our model on real-world data in different domains and examine our model's generalizability across various datasets. Our experimental analysis demonstrates our approach's superiority in accuracy and efficiency. In particular, we speed up the prior state-of-the-art by more than 100× on the benchmark datasets while maintaining an error rate below 0.1%.

Persistence diagrams have been widely used to quantify the underlying features of filtered topological spaces in data visualization. In many applications, computing distances between diagrams is essential; however, computing these distances has been challenging due to the computational cost. In this paper, we propose a persistence diagram hashing framework that learns a binary code representation of persistence diagrams, which allows for fast computation of distances. This framework is built upon a generative adversarial network (GAN) with a diagram distance loss function to steer the learning process. Instead of using standard representations, we hash diagrams into binary codes, which have natural advantages in large-scale tasks. The training of this model is domain-oblivious in that it can be computed purely from synthetic, randomly created diagrams. As a consequence, our proposed method is directly applicable to various datasets without the need for retraining the model. These binary codes, when compared using fast Hamming distance, better maintain topological similarity properties between datasets than other vectorized representations. To evaluate this method, we apply our framework to the problem of diagram clustering and we compare the quality and performance of our approach to the state-of-the-art. In addition, we show the scalability of our approach on a dataset with 10k persistence diagrams, which is not possible with current techniques. Moreover, our experimental results demonstrate that our method is significantly faster with the potential of less memory usage, while retaining comparable or better quality comparisons.

We study the interplay between the recently-defined concept of minimum homotopy area and the classical topic of self-overlapping curves. The latter are plane curves that are the image of the boundary of an immersed disk. Our first contribution is to prove new sufficient combinatorial conditions for a curve to be self-overlapping. We show that a curve γ with Whitney index 1 and without any self-overlapping subcurves is self-overlapping. As a corollary, we obtain sufficient conditions for self-overlapping ness solely in terms of the Whitney index of the curve and its subcurves. These results follow from our second contribution, which shows that any plane curve γ, modulo a basepoint condition, is transformed into an interior boundary by wrapping around γ with Jordan curves. In fact, we show that n+1 wraps suffice, where γ has n vertices. Our third contribution is to prove the equivalence of various definitions of self-overlapping curves and interior boundaries, often implicit in the literature. We also introduce and characterize zero-obstinance curves, a further generalization of interior boundaries defined by optimality in minimum homotopy area.

Exposure to science, technology, engineering, and mathematics (STEM) at a young age is key to inspiring students to pursue careers in these fields. Thus, many institutions of higher education offer events to engage youth in STEM activities. These events are most effective when they are adapted to the specific audience. In Montana, a large percentage of the K-12 student population is from rural communities, where the ability to participate in such events is limited due to travel logistics and a shortage of relatable materials. We have developed a computer science outreach module that targets these populations through the use of storytelling and the Alice programming environment, thus drawing a parallel between storytelling and building algorithms. We describe the module's implementation, report and analyze feedback, and provide lessons learned from the module's implementation at outreach events.

Montana is home to a large American Indian population and a rich history. The Indian Education for All (IEFA) Act, passed in 1999, reinforces the educational goals stated in Montana's 1972 Constitution that "every Montanan, whether Indian or non-Indian, be encouraged to learn about the distinct and unique heritage of American Indians in a culturally responsive manner." IEFA requires that American Indian education be integrated into "the education of each Montana citizen," making Montana the only state to mandate Indian education by law. We propose an integration of CS concepts into existing content standards using the IEFA curricula. To make these concepts approachable, we utilize Alice, a drag-and-drop programming environment. This software allows students to animate stories while learning programming techniques in a user-friendly way. Furthermore, Alice 2 allows customized models; in particular, we can create models specific to American Indian culture. In this poster, we present an overview of the Storytelling project and preliminary results, an example lesson plan, evaluation techniques, and a description of the 3D model creation process. With these lesson plans and customized models, we strive to broaden participation of students from rural and American Indian communities in CS and related fields.

We propose a new approach for constructing the underlying map from trajectory data. Our algorithm is based on the idea that road segments can be identified as stable subtrajectory clusters in the data. For this, we consider how subtrajectory clusters evolve for varying distance values, and choose stable values for these. In doing so we avoid a global proximity parameter. Within trajectory clusters, we choose representatives, which are combined to form the map. We experimentally evaluate our algorithm on vehicle and hiking tracking data. These experiments demonstrate that our approach can naturally separate roads that run close to each other and can deal with outliers in the data, two issues that are notoriously difficult in road network reconstruction.

Topological data analysis (TDA) has rapidly grown in popularity in recent years. One of the emerging tools is persistent local homology, which can be used to extract local structure from a dataset. In this paper, we provide a survey that explores this new tool, emphasizing its use in data analysis.

Due to the ubiquitous use of various positioning technologies in smart phones and other devices, geospatial tracking data has become a routine data source. One of its uses that has gained recent popularity is the construction of street maps from vehicular tracking data. Due to the inherent noise in the data, many map construction algorithms are based on thresholding a density function. While kernel density estimation provides a firm theoretical foundation for computing the density from the measurements, the thresholds are generally picked in a heuristic, and often brute-force way, which results in slow algorithms with no guarantees on the map construction quality.

Persistent homology is a multiscale method for analyzing the shape of sets and functions from point cloud data arising from an unknown distribution supported on those sets. When the size of the sample is large, direct computation of the persistent homology is prohibitive due to the combinatorial nature of the existing algorithms. We propose to compute the persistent homology of several subsamples of the data and then combine the resulting estimates. We study the risk of two estimators and we prove that the subsampling approach carries stable topological information while achieving a great reduction in computational complexity.

BACKGROUND: Tumorigenesis is an evolutionary process by which tumor cells acquire mutations through successive diversification and differentiation. There is much interest in reconstructing this process of evolution due to its relevance to identifying drivers of mutation and predicting future prognosis and drug response. Efforts are challenged by high tumor heterogeneity, though, both within and among patients. In prior work, we showed that this heterogeneity could be turned into an advantage by computationally reconstructing models of cell populations mixed to different degrees in distinct tumors. Such mixed membership model approaches, however, are still limited in their ability to dissect more than a few well-conserved cell populations across a tumor data set. RESULTS: We present a method to improve on current mixed membership model approaches by better accounting for conserved progression pathways between subsets of cancers, which imply a structure to the data that has not previously been exploited. We extend our prior methods, which use an interpretation of the mixture problem as that of reconstructing simple geometric objects called simplices, to instead search for structured unions of simplices called simplicial complexes that one would expect to emerge from mixture processes describing branches along an evolutionary tree. We further improve on the prior work with a novel objective function to better identify mixtures corresponding to parsimonious evolutionary tree models. We demonstrate that this approach improves on our ability to accurately resolve mixtures on simulated data sets and demonstrate its practical applicability on a large RNASeq tumor data set. CONCLUSIONS: Better exploiting the expected geometric structure for mixed membership models produced from common evolutionary trees allows us to quickly and accurately reconstruct models of cell populations sampled from those trees. In the process, we hope to develop a better understanding of tumor evolution as well as other biological problems that involve interpreting genomic data gathered from heterogeneous populations of cells.

Persistent homology is a widely used tool in Topological Data Analysis that encodes multiscale topological information as a multi-set of points in the plane called a persistence diagram. It is difficult to apply statistical theory directly to a random sample of diagrams. Instead, we can summarize the persistent homology with the persistence landscape, introduced by Bubenik, which converts a diagram into a well-behaved real-valued function. We investigate the statistical properties of landscapes, such as weak convergence of the average landscapes and convergence of the bootstrap. In addition, we introduce an alternate functional summary of persistent homology, which we call the silhouette, and derive an analogous statistical theory.

We define a topology-based distance metric between road networks embedded in the plane. This distance measure is based on local persistent homology, and employs a local distance signature that enables identification and visualization of local differences between the road networks. This paper is motivated by the need to recognize changes in road networks over time and to assess the quality of different map construction algorithms. One particular challenge is evaluating the results when no ground truth is known. However, we demonstrate that we can overcome this hurdle by using a statistical technique known as the bootstrap.

We present an efficient algorithm for solving a linear system arising from the 1-Laplacian corresponding to a collapsible simplicial complex with a known collapsing sequence. When combined with a result of Chillingworth, our algorithm is applicable to convex simplicial complexes embedded in ℝ3. The running time of our algorithm is nearly-linear in the size of the complex and is logarithmic on its numerical properties. Our algorithm is based on projection operators and combinatorial steps for transferring between them. The former relies on decomposing flows into circulations and potential flows using fast solvers for graph Laplacians, and the latter relates Gaussian elimination to topological properties of simplicial complexes.

It has been an open question whether the sum of finitely many isotropic Gaussian kernels in n ≥ 2 dimensions can have more modes than kernels, until in 2003 Carreira-Perpinan and Williams exhibited n+1 isotropic Gaussian kernels in Rn with n+2 modes. We give a detailed analysis of this example, showing that it has exponentially many critical points and that the resilience of the extra mode grows like √n. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes.