Research
My research interests are in computational topology and geometry, combinatorial topology, and applied topology (in particular to data analysis and to sensor networks).
I am a member of the Pattern Analysis Lab.
Here is my PhD thesis, a related research highlight, and an outdated research statement.
Papers on VietorisRips and Čech complexes
For X a finite subset of the circle and for 0 < r ≤ 1 fixed, consider the function f_{r} : X → X which maps each point to the clockwise furthest element of X within angular distance less than 2πr. We study the discrete dynamical system on X generated by f_{r} , and especially its expected behavior when X is a large random set. We show that the expected fraction of periodic points of f_{r} is 0 if r is irrational and 1/q if r = p/q is rational with p and q coprime. These results are obtained via more refined statistics of f_{r} which we compute explicitly in terms of (generalized) Catalan numbers. The motivation for studying f_{r} comes from VietorisRips complexes, a geometric construction used in computational topology. Our results determine how much one can expect to simplify the VietorisRips complex of a random sample of the circle by removing dominated vertices.
Given a metric space X and a distance threshold r > 0, the VietorisRips simplicial complex has as its simplices the finite subsets of X of diameter less than r. A theorem of JeanClaude Hausmann states that if X is a Riemannian manifold and r is sufficiently small, then the VietorisRips complex is homotopy equivalent to the original manifold. Little is known about the behavior of VietorisRips complexes for larger values of r, even though these complexes arise naturally in applications using persistent homology. We show that as r increases, the VietorisRips complex of the circle obtains the homotopy types of the circle, the 3sphere, the 5sphere, the 7sphere, ..., until finally it is contractible. As our main tool we introduce a directed graph invariant, the winding fraction, which in some sense is dual to the circular chromatic number. Using the winding fraction we classify the homotopy types of the VietorisRips complex of an arbitrary (possibly infinite) subset of the circle, and we study the expected homotopy type of the VietorisRips complex of a uniformly random sample from the circle. Moreover, we show that as the distance parameter increases, the ambient Čech complex of the circle also obtains the homotopy types of the circle, the 3sphere, the 5sphere, the 7sphere, ..., until finally it is contractible.


Nerve complexes of circular arcs.
With Michał Adamaszek, Florian Frick, Chris Peterson, and Corrine PreviteJohnson.
[arXiv:1410.4336,
Abstract]

We show that the nerve complex of n arcs in the circle is homotopy equivalent to either a point, an odddimensional sphere, or a wedge sum of spheres of the same even dimension. Moreover this homotopy type can be computed in time O(n log n). For the particular case of the nerve complex of evenlyspaced arcs of the same length, we determine the dihedral group action on homology, and we relate the complex to a cyclic polytope with n vertices. We give three applications of our knowledge of the homotopy types of nerve complexes of circular arcs. First, we use the connection to cyclic polytopes to give a novel topological proof of a known upper bound on the distance between successive roots of a homogeneous trigonometric polynomial. Second, we show that the Lovász bound on the chromatic number of a circular complete graph is either sharp or off by one. Third, we show that the VietorisRips simplicial complex of $n$ points in the circle is homotopy equivalent to either a point, an odddimensional sphere, or a wedge sum of spheres of the same even dimension, and furthermore this homotopy type can be computed in time O(n log n).
Papers on sensor networks
Suppose that ballshaped sensors wander in a bounded domain. A sensor doesn't know its location but does know when it overlaps a nearby sensor. We say that an evasion path exists in this sensor network if a moving intruder can avoid detection. In "Coordinatefree coverage in sensor networks with controlled boundaries via homology", Vin de Silva and Robert Ghrist give a necessary condition, depending only on the timevarying connectivity data of the sensors, for an evasion path to exist. Using zigzag persistent homology, we provide an equivalent condition that moreover can be computed in a streaming fashion. However, no method with timevarying connectivity data as input can give necessary and sufficient conditions for the existence of an evasion path. Indeed, we show that the existence of an evasion path depends not only on the fibrewise homotopy type of the region covered by sensors but also on its embedding in spacetime. For planar sensors that also measure weak rotation and distance information, we provide necessary and sufficient conditions for the existence of an evasion path.
Papers on data analysis


Persistent images: A stable vector representation of persistent homology.
With Sofya Chepushtanova, Tegan Emerson, Eric Hanson, Michael Kirby, Francis Motta, Rachel Neville, Chris Peterson, Patrick Shipman, and Lori Ziegelmeier.
[arXiv:1507.06217,
Abstract]

Many data sets can be viewed as a noisy sampling of an underlying topological space. A suite of tools in topological data analysis allows one to exploit this structure for the purpose of knowledge discovery. One such tool is persistent homology which provides a multiscale description of the homological features within a data set. A useful representation of this homological information is a persistence diagram (PD). The space of PDs can be given a metric structure allowing a given diagram to be used as a statistic for the purpose of comparison against other diagrams. We convert a PD to a persistence image (PI) and prove stability with respect to small perturbations in the inputs. The PI is a vector representation allowing the application of vectorbased machine learning tools, such as linear and sparse support vector machines. These tools help to identify discriminatory features which can have a topological interpretation. The PIs and PDs derived from randomly sampled topological spaces are compared by applying the Kmedoids clustering algorithm. To further illustrate the PI technique, linear and sparse support vector machines are implemented on this data set and classification is performed on additional data arising from a discrete dynamical system called the linked twist map.
We use the nudged elastic band method from computational chemistry to analyze highdimensional data. Our approach is inspired by Morse theory, and as output we produce an increasing sequence of small cell complexes modeling the dense regions of the data. We test the method on data sets arising in social networks and in image processing. Furthermore, we apply the method to identify new topological structure in a data set of optical flow patches.
Carlsson, Ishkanov, de Silva, and Zomorodian apply computational topological tools to the data set of 3 × 3 patches from optical images studied by Lee, Pedersen, and Mumford and find geometric structures for high density subsets. One high density subset is called the primary circle and essentially consists of patches with a line separating a light and a dark region. In this paper, we apply the techniques of Carlsson et al. to range patches. By enlarging to 5 × 5 and 7 × 7 patches, we find core subsets that have the topology of the primary circle, suggesting a stronger connection between optical patches and range patches than was found by Lee, Pedersen, and Mumford.
Conference proceedings
The computation of persistent homology has proven a fundamental component of the nascent field of topological data analysis and computational topology. We describe a new software package for topological computation, with design focus on needs of the research community. This tool, replacing previous jPlex and Plex, enables researchers to access state of the art algorithms for persistent homology, cohomology, hom complexes, filtered simplicial complexes, filtered cell complexes, witness complex constructions, and many more essential components of computational topology. We describe the design goals we have chosen, the resulting software package, and some of its more novel capabilities.
Software tutorials