Search for: All records

This paper presents the first approach to visualize the importance of topological features that define classes of data. Topological features, with their ability to abstract the fundamental structure of complex data, are an integral component of visualization and analysis pipelines. Although not all topological features present in data are of equal importance. To date, the default definition of feature importance is often assumed and fixed. This work shows how proven explainable deep learning approaches can be adapted for use in topological classification. In doing so, it provides the first technique that illuminates what topological structures are important in each dataset in regards to their class label. In particular, the approach uses a learned metric classifier with a density estimator of the points of a persistence diagram as input. This metric learns how to reweigh this density such that classification accuracy is high. By extracting this weight, an importance field on persistent point density can be created. This provides an intuitive representation of persistence point importance that can be used to drive new visualizations. This work provides two examples: Visualization on each diagram directly and, in the case of sublevel set filtrations on images, directly on the images themselves. This work highlights real-world examples of this approach visualizing the important topological features in graph, 3D shape, and medical image data. 

The Fréchet distance is often used to measure distances between paths, with applications in areas ranging from map matching to GPS trajectory analysis to hand- writing recognition. More recently, the Fréchet distance has been generalized to a distance between two copies of the same graph embedded or immersed in a metric space; this more general setting opens up a wide range of more complex applications in graph analysis. In this paper, we initiate a study of some of the fundamental topological properties of spaces of paths and of graphs mapped to R^n under the Fréchet distance, in an eort to lay the theoretical groundwork for understanding how these distances can be used in practice. In particular, we prove whether or not these spaces, and the metric balls therein, are path-connected. 

Blank, in his Ph.D. thesis on determining whether a planar closed curve $\gamma$ is self-overlapping, constructed a combinatorial word geometrically over the faces of $\gamma$ by drawing cuts from each face to a point at infinity and tracing their intersection points with $\gamma$. Independently, Nie, in an unpublished manuscript, gave an algorithm to determine the minimum area swept out by any homotopy from a closed curve $\gamma$ to a point. Nie constructed a combinatorial word algebraically over the faces of $\gamma$ inspired by ideas from geometric group theory, followed by dynamic programming over the subwords. In this paper, we examine the definitions of the two words and prove the equivalence between Blank's word and Nie's word under the right assumptions. 

In 2021, National Science Foundation (NSF) Computer and Information Science and Engineering (CISE) directorate implemented a Broadening Participation in Computing (BPC) plan requirement for all medium and larger research proposals in Core, CPS, and SaTC. This panel comprises faculty and administrators from US computing departments who have participated in the writing of Departmental or Project BPC plans, two in response to NSF’s encouragement and one prior. Panelists represent a range of institutions as well as departmental awareness of BPC prior to writing their plans. Regardless of where they or their departments lie in the spectrum of knowing about and implementing BPC activities, and regardless of the current demographic makeup of the students in their major, they all encountered challenges as they wrote their plans. They all also experienced successes, not the least of which is that they succeeded in getting a plan written in accordance with the current guidelines. With the support of a moderator, the three panelists will share their experiences developing BPC plans with the audience, offering lessons learned and tips for overcoming common challenges. Audience members will also receive helpful links and handouts to facilitate the writing of their own departmental or project plans 

Persistent homology is a tool that can be employed to summarize the shape of data by quantifying homological features. When the data is an object in R d , the (augmented) persistent homology transform ((A)PHT) is a family of persistence diagrams, parameterized by directions in the ambient space. A recent advance in understanding the PHT used the framework of reconstruction in order to find finite a set of directions to faithfully represent the shape, a result that is of both theoretical and practical interest. In this paper, we improve upon this result and present an improved algorithm for graph— and, more generally one-skeleton—reconstruction. The improvement comes in reconstructing the edges, where we use a radial binary (multi-)search. The binary search employed takes advantage of the fact that the edges can be ordered radially with respect to a reference plane, a feature unique to graphs. 

Graphs in metric spaces appear in a wide range of data sets, and there is a large body of work focused on comparing, matching, or analyzing collections of graphs in different ambient spaces. In this survey, we provide an overview of a diverse collection of distance measures that can be defined on the set of finite graphs immersed (and in some cases, embedded) in a metric space. For each of the distance measures, we recall their definitions and investigate which of the properties of a metric they satisfy. Furthermore we compare the distance measures based on these properties and discuss their computational complexity.

 

Since its introduction in the mid-1990s, DBSCAN has become one of the most widely used clustering algorithms. However, one of the steps in DBSCAN is to perform a range query, a task that is difficult in many spaces, including the space of persistence diagrams. In this paper, we introduce a spanner into the DBSCAN algorithm to facilitate range queries in such spaces. We provide a proof-of-concept implementation, and study time and clustering performance for two data sets of persistence diagrams. 

In July 2021, Computer Science (CS) standards were officially added as a subject area within the K-12 Montana content standards. However, due to a lack of professional development and pre-service preparation in CS, schools and teachers in Montana are underprepared to implement these standards. Montana is also a unique state, since American Indian education is mandated by the state constitution in what is known as the Indian Education for All Act. We are developing elementary and middle school units and teacher training materials that simultaneously address CS, Indian Education, and other Montana content standards. In this paper, we present a unit for fourth through sixth grades using a participatory design approach. Through physical computing, students create a visual narrative of their own stories inspired by ledger art, an American Indian art medium for recording lived experiences. We discuss the affordances and challenges of an integrated approach to CS teaching and learning in elementary and middle schools in Montana.