Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

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 realworld examples of this approach visualizing the important topological features in graph, 3D shape, and medical image data.more » « lessFree, publiclyaccessible full text available October 22, 2024

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 pathconnected.more » « lessFree, publiclyaccessible full text available July 31, 2024

Morin, Pat ; Suri, Subhash (Ed.)Let γ be a generic closed curve in the plane. Samuel Blank, in his 1967 Ph.D. thesis, determined if γ is selfoverlapping by geometrically constructing a combinatorial word from γ. More recently, Zipei Nie, in an unpublished manuscript, computed the minimum homotopy area of γ by constructing a combinatorial word algebraically. We provide a unified framework for working with both words and determine the settings under which Blank’s word and Nie’s word are equivalent. Using this equivalence, we give a new geometric proof for the correctness of Nie’s algorithm. Unlike previous work, our proof is constructive which allows us to naturally compute the actual homotopy that realizes the minimum area. Furthermore, we contribute to the theory of selfoverlapping curves by providing the first polynomialtime algorithm to compute a selfoverlapping decomposition of any closed curve γ with minimum area.more » « less

Blank, in his Ph.D. thesis on determining whether a planar closed curve $\gamma$ is selfoverlapping, 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.more » « less

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 plansmore » « less

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 oneskeleton—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.more » « less

Abstract 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 mid1990s, 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 proofofconcept implementation, and study time and clustering performance for two data sets of persistence diagrams.more » « less