Workshop on Computational Topology at SoCG 2012
Organizers: Paul Bendich, Herbert Edelsbrunner, Dmitriy Morozov
Tuesday, June 19
Time 
Speaker 
Title + Abstract 
4:05pm 
Erin Chambers 
Title: Topological measures of similarity
Abstract:
The question of how to measure similarity between curves in various
topological spaces has received much attention recently.
Possibilities for comparing curves include the Frechet distance (and
its variants such as geodesic, homotopic, and isotopic Frechet
distance), homotopy height, and deformation area (or the area of the
homotopy); many of these have algorithms in settings that range from
the plane to combinatorial surfaces to cell complexes. We will
compare and survey known results as well as recent progress and open
questions in several of these settings.

4:35pm 
David Salinas 
Title: Simplification of simplicial complexes, towards the intrinsic dimension
Abstract:
Given a set of points that sample a shape, it has been proved recently that
under some density requirements the Rips complex of the points provides an
approximation of the shape with the correct homotopy type.
One advantage of the Rips complex is that it is determined entirely by its
1skeleton which provides a compact form of storage. Unfortunately, the
dimension of the Rips complex can be huge, compared to the intrinsic dimension
of the shape.
We will describe different strategies for simplifying the Rips complex and
obtain a simplicial complex whose dimension is that of the sampled shape. In
particular, we will present the beginning of some theorical work which aims at
explaining the good behaviour of our simplification strategies in practice.

5:05pm 
break 
5:20pm 
Mikael VejdemoJohansson 
Title: Algebraic Persistence
Abstract:
Persistent homology was shown by Zomorodian and Carlsson to be accurately
modeled as homology with coefficients in the polynomial ring k[t]. Much of the
body of work in the community since these results has assumed free chain
complexes: torsion on a chain level remains an essentially unsolved problem.
We develop ideas from computational commutative algebra to produce purely
algebraic tools to approach persistence modules. These ideas provide purely
algebraic approaches to the computation of finite presentations of various
modules, such as images, kernels and cokernels of maps between persistence
modules, paralleling work by CohenSteiner, Edelsbrunner, Harer and Morozov. The
algebraic approach produces two tangible benefits: chain complexes with torsion
are clear to handle, and with this, relative homology  and with this, both
local and extended persistent homology  becomes accessible without relying on
long exact sequences or on cone constructions.
(Joint work with Primoz Skraba.)

5:50pm 
Daniel Muellner 
Title:
Consistent scale selection for exploratory visualization and analysis of data sets
Abstract:
Choosing an appropriate scale is a frequently encountered problem in data
analysis, and paradigms in the field support both the choice of strategies to
make smart, definite choices and the hierarchical or persistence approach of
looking at all scales at once. In the core of the “Mapper” algorithm for
visualization and analysis of point cloud data, a scale choice must be made
multiple times for overlapping fragments of the data set. We present the concept
of a scale graph, where scale choices in neighboring regions are
brought into conjunction to make consistent decisions at local scale, while
retaining global flexibility. By selecting an optimal path through the scale
graph, we can make more plausible choices, overcome existing weaknesses,
validate results more easily and simplify the data analysis process for the
user.
(Joint work with Gunnar Carlsson, Facundo Mémoli, Gurjeet Singh.)

Wednesday, June 20
Time 
Speaker 
Title + Abstract 
2:20pm 
Amit Patel 
Title:
On the Stability of Preimages
Abstract:
Given a real valued map, persistence allows one to quantify the stability of the
homology of its sublevel sets to perturbations of the map. Given a continuous
map to a manifold M and a point p in M, how stable is the homology of the
preimage of p? The well group addresses this basic question. Using pictures, I
will motivate this question and introduce the basic definitions.

2:50pm 
Brittany Fasy 
Title:
Persistence of Extra Modes in Gaussian Mixtures
Abstract:
The sum of finitely many isotropic Gaussian kernels in 2 or higherdimensional
Euclidean space can have more modes than kernels. Even more surprising is the
fact that the sum can have an exponential number of critical values. We
consider the sum of Gaussians where the means of the Gaussians are located at
the vertices of a regular nsimplex in R^n. Normalizing the mixture to obtain a
probability distribution, we focus our attention on the extra mode that appears
at the barycenter of the simplex. In particular, we investigate how the
persistence of the mode at the barycenter changes with respect to increasing
dimension.

3:20pm 
Fengtao Fan 
Title:
Computing persistence for simplicial maps and its application to Rips complexes
Abstract:
It is known that persistent homology and zigzag persistent homology are well
defined for homology modules where homomorphisms need not be induced by
inclusion maps. However, there are no practical algorithms for general homology
homomorphisms except the algorithm in Gunnar Carlsson and Vin De Silva [2008]
which works by operating on the matrices representing the homomorphisms. In
this talk, we propose a practical algorithm for computing persistence and zigzag
persistence for a sequence of general simplicial maps. We leverage the fact that
every simplicial map can be simulated by inclusion maps. Therefore, computing
the zigzag persistent homology for simplicial map is not more difficult than for
inclusion maps. With this new tool, we develop a new algorithm to approximate
the persistence diagram of a filtration of Rips complexes induced by inclusion
maps.
(This is an ongoing work with Tamal Dey and Yusu Wang at the Ohio State
University.)

3:50pm 
break 
4:20pm 
Jennifer Gamble 
Title:
Zigzag Persistent Homology in TimeVarying Sensor Networks
Abstract:
Methods from applied algebraic topology have been successfully employed to study
coverage properties of coordinatefree sensor networks. In this setting, tools
from homology are used to compute the presence of `holes' in the coverage area
of the network, using only local information from each sensor. Here, we
consider a timevarying sensor network observed in at discrete time points, and
leverage zigzag persistence to track the homology of this sequence of spaces.
This gives a way to distinguish between `persistent' coverage holes due to an
underlying problem, and transient holes due to the dynamic nature of the
network.

4:50pm 
Elizabeth Munch 
Title:
Metrics on Vineyards
Abstract:
Computational topology has become an excellent tool for analyzing static point
clouds, but what happens when the point clouds move? With the introduction of
vineyards came the analogue to the persistence diagram, but unlike the
persistence diagram, there is no obvious notion of distance between two
vineyards. In order to compare two dynamic point clouds and their corresponding
vineyards, we will look at some options for metrics on vineyards. These metrics
arose from looking at point clouds which represent primate group fission and
fusion.

5:20pm 
Bei Wang 
Title:
Sampling for Local Homology with VietorisRips Complexes
Abstract:
Recently, a multiscale notion of local homology was
proposed by Bendich et. al. to study the local structure of a
stratified space around a given point from a point cloud sample. To
give reconstruction guarantees, the approach relied on constructing
embedded complexes which become difficult to construct in high
dimensions. We derive sampling conditions under which the persistence
diagrams used for estimating local homology, can be approximated using
families of VietorisRips complexes, whose simple construction is
robust in any dimension. To the best of our knowledge, our results,
for the first time, make stratification learning using local homology
feasible in highdimensions.
(Joint work with Primoz Skraba.)
