May 17, 2024

July - December 2011
Thematic Program on Discrete Geometry and Applications

Proposed talks, title and abstract, November Workshops
Accepted talks will be 20 to 30 minutes in length.

November 7-11, 2011
Workshop on Computational Topology

Bauer, Ulrich
Optimal Topological Simplification of Functions on Surfaces

Persistent homology quantifies the stability of critical points of a scalar function: a critical point with large persistence cannot be eliminated by a small perturbation. Motivated by the fact that noise can give rise to spurious critical points, we consider the converse problem: within a prescribed tolerance from some input function, minimize the number of critical points.
For functions on surfaces, we solve this problem using a novel combination of persistent homology and discrete Morse theory. We construct a function that achieves the lower bound on the number of critical points dictated by the stability of persistence diagrams. Such a function can be constructed in linear time after persistence pairs have been identified.
Moreover, we obtain not only a single solution but a whole a convex set of optimal solutions. Within this set, a convex functional can be minimized using convex optimization methods, guaranteeing that the minimum number of critical points is still maintained.
(Joint work with Carsten Lange and Max Wardetzky. Reference:

Bobrowski, Omer and Robert J. Adler
Distance Functions, Critical Points, and Topology for some Random Complexes

In this talk we focus on the distance function from a random set of points $P$ in the Euclidean space. The distance function is continuous, however, it is not everywhere differentiable. Nevertheless, one can accurately define critical points and then apply Morse theory to it.We study the number of critical points in small neighborhoods around $P$.
Specifically, we are interested in the case where the number of points in $P$ goes to infinity, and the size of the neighborhoods goes to zero. We present limit theorems for the number of critical points and show that it exhibits a phase transition, depending on how fast the size of the neighborhoods goes to zero. A similar phase transition was presented recently by Kahle & Meckes who studied the Betti-numbers of random geometric complexes.
We show that this is more than just a coincidence, and discuss the connection between the distance function and geometric complexes.

Cerri, Andrea and Frosini, Patrizio
Approximation Algorithm for the Multidimensional Mathching Distance

Topological Persistence has proven to be a promising framework for dealing with problems concerning shape analysis and comparison. In this context, it was originally introduced by taking into account 1-dimensional properties of shapes, modeled by real-valued functions. More recently, Topological Persistence has been generalized to consider multidimensional properties of shapes, coded by vector-valued functions. This extension has led to introduce suitable shape descriptors, named the multidimensional persistence Betti numbers, and a distance to compare them, the socalled multidimensional matching distance. In this paper we propose a new computational framework to deal with the multidimensional matching distance. We start by showing some theoretical results, and then we use them to formulate an algorithm for computing such a distance up to an arbitrary threshold error.

Attali, Dominique & Lieutier, Andre & Salinas, David
Efficient Data Structure for Representing and Simplifying Simplicial Complexes in High Dimensions

We study the simplification of simplicial complexes by repeated edge contractions. First, we extend to arbitrary simplicial complexes the statement that edges satisfying the link condition can be contracted while preserving the homotopy type. Our primary interest is to simplify flag complexes such as Rips complexes for which it was proved recently that they can provide topologically correct reconstructions of shapes. Flag complexes (sometimes called clique complexes) enjoy the nice property of being completely determined by the graph of their edges. But, as we simplify a flag complex by repeated edge contractions, the property that it is a flag complex is likely to be lost. Our second contribution is to propose a new representation for simplicial complexes particularly well adapted for complexes close to flag complexes. The idea is to encode a simplicial complex $K$ by the graph $G$ of its edges together with the inclusion-minimal simplices in the set difference $Flag(G) \ K$. We call these minimal simplices blockers. We prove that the link condition translates nicely in terms of blockers and give formulae for updating our data structure after an edge contraction or a collapse. Finally, we observe in some simple cases that few blockers appear during the simplification of Rips complexes, demonstrating the efficiency of our representation in this context.

Lieutier, Andre & Attali, Dominique & Salinas, David
Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes

We associate with each compact set $X$ of Rn two real-valued functions $cX$ and $hX$ defined on $R+$ which provide two measures of how much the set $X$ fails to be convex at a given scale. First, we show that, when P is a finite point set, an upper bound on cP (t) entails that the Rips complex of P at scale r collapses to the Cech complex of P at scale r for some suitable values of the parameters t and r. Second, we prove that, when P samples a compact set X, an upper bound on hX over some interval guarantees a topologically correct reconstruction of the shape X either with a Cech complex of $P$ or with a Rips complex of P. Regarding the reconstruction with Cech complexes, our work compares well with previous approaches when X is a smooth set and surprisingly enough, even improves constants when X has a positive mu-reach. Most importantly, our work shows that Rips complexes can also be used to provide topologically correct reconstruction of shapes. This maybe of some computational interest in high dimensions.

Chazal, Frederic
Persistence Based Signatures for Metric Spaces

We introduce a family of signatures for compact metric spaces, possibly endowed with real valued functions, based on the persistence diagrams of suitable filtrations built on top of these spaces. We prove the stability of these signatures under Gromov-Hausdorff perturbations of the spaces.

Dey, Tamal K. Ohio State University
Computing Homology Cycles with Certified Geometry

Computation of cycles representing classes of homology groups is a fundamental problem arising in applications such as parameterization, feature identification, topology simplification, and data analysis. Variations of the classical Smith Normal Form algorithm and the recently developed persistence algorithm do compute representative cycles of a homology basis for a simplicial complex, but they remain oblivious to the input geometry. Some recent research in computational topology has addressed the problems of computing homology cycles that are optimal with respect to a given metric. In this talk, we concentrate on two such developments: (i) Computing an optimal basis for one dimensional homology of a simplicial complex and using it to approximate such a basis for a smooth manifold from its point data; (ii) Computing an optimal cycle homologous to a given cycle in a simplicial complex. We provide efficient algorithms with their guarantees for (i) and show that classical Linear Programs can solve (ii) for some interesting cases even though the general problem is NP-hard.

Dlotko, Pawel
Applications of Computational (co)homology

Due to the recent development of efficient algorithms and implementations, homology and cohomology theories have become useful tools in various branches of science and engineering. For example, electromagnetic modeling provides an interesting context to present a link between physical phenomena and homology and cohomology. Over the past twenty-five years a considerable effort has been invested by the computational electromagnetics community to develop fast and general techniques for potential design. Nevertheless, heuristic approaches seem still to be dominant in literature. During the talk a proof will be given showing that, for edge-element based finite element method, the first cohomology group generators are needed to make boundary value problem well defined. To conclude, efficient algorithmic techniques to compute cohomology group generators on various meshes (being arbitrary regular CW-complexes) will be presented together with results of electromagnetic simulations (this is joint work with Ruben Specogna).
If time permits, recent progress in distributed (co)homology computations will be discussed. As an example, a coverage problem in sensor network will be presented and distributed computation techniques used to solve it will be highlighted (joint work with Robert Ghrist, Mateusz Juda and Marian Mrozek).

Gonzalez-Dias, Rocio
Algebraic Topological Tools for Combinatorial Image Analysis

The field of image analysis studies the topology and geometry of digital images and data sets. The subfield of combinatorial image analysis studies their combinatorial properties. Algebraic topology is a field of mathematics concerned with the study of deformation-invariant properties of geometrical objects. Our recently created Andalusian research group FQM-369 “Combinatorial Image Analysis” develops methods and tools for combinatorial image analysis, which apply the theory of computational topology. In this talk, we will introduce the three main tasks in which our group is involved:
(1) Well-composed cell complexes. The 2D manifold that is the surface bounding a real 3D object, might appear to be non-manifold in the geometric realization of the cubical complex Q(I) associated to a discrete representation of the object after the acquisition process. This task deals with the construction of a cell complex K(I) that is homotopy equivalent to Q(I) and whose boundary surface is a union of 2D manifolds.
(2) Cup products on general cell complexes. The cup product on cohomology encodes more information than homology, but has traditionally been computed only for cubical and simplicial complexes. Recently our group developed techniques that allow to compute the cup product on cell complexes X, where X is a quotient, a Cartesian product, or the result of merging cells of highest dimension.
(3) Extending persistent homology. The incremental algorithm for persistent homology by Edelsbrunner et al., is currently the de facto standard for extracting topological information, especially Betti numbers, when an object is seen as a sequence of additions from a point cloud data. A first aim of this task is to extend persistent homology to cell complexes obtained from the given one by merging, removing cells or edge contractions.
Collaborators: Maria Jose Jimenez and Belen Medrano (Applied Math Dept., University of Seville, Spain), Walter G. Kropatsch (PRIP group, Vienna University of Technology, Austria), Adrian Ion (PRIP group and Institute of Science and Technology, Austria), Ron Umble (Math. Dept., Millersville University of Pennsylvania, USA).

Frosini, Patrizio (speaker) and Barbara Di Fabio University of Bologna
Filtrations Induced by Continuous Functions

Filtrations are at the core of some topological data analysis methods. For instance, persistent homology captures the topology of a space by measuring the lifetime of homological events occurring along a given filtration. These kinds of filtration are often induced by considering sub-level sets of continuous functions. A natural question arises about whether any filtration can be generated in this way. In our talk we analyze this problem. In particular, we present a result showing that, under some "natural" conditions, any filtration of a topological space is induced by a continuous function. Both the cases of scalar and vector indexed filtrations are considered.

Hirani, Anil University of Illinois
Optimization, Knots, and Differential Equations

I will introduce several optimality problems in integer homology and real cohomology that we have studied recently. For integer homology, I will first discuss our STOC 2010 result for the Optimal Homologous Chain Problem (OHCP). We showed that for relatively torsion-free complexes, OHCP can be solved in polynomial time. This was surprising because with mod 2 coefficients OHCP is NP-hard, as shown earlier by Chen and Freedman. Next I will describe our SoCG 2011 result by introducing the Optimal Bounding Chain Problem (OBCP) and its relative version. We used these to show that the Least Spanning Area Problem for knots embedded in 3-manifolds with trivial homology can be solved in polynomial time. An earlier result of Agol, Hass, and Thurston is that for general 3-manifolds the problem is NP-hard. Both OHCP and OBCP discussed above were formulated as 1-norm minimization while satisfying some constraint involving boundary matrices. If instead, one uses 2-norm minimization, real coefficients, and coboundary matrices, the OHCP problem transforms into one that is needed as a fundamental step in finite element exterior calculus for solving elliptic partial differential equations. I will discuss our recent results from our arXiv eprint on Cohomologous Harmonic Cochains where we proved a discrete Hodge-deRham isomorphism theorem. Different parts of the above results are joint work with T. Dey, N. Dunfield, K. Kalyanaraman, B. Krishnamoorthy, S. Watts, and H. Wang.

Kaczynski, Tomasz Universite de Sherbrooke
Computing Cohomology Ring

In the past decades, the homology and cohomology theories gained a vivid attention outside of the mathematics community prompted by its modern applications in sciences and engineering. Until recently, the main progress has been done in computation of homology groups of finitely representable objects. Whenever a mathematical model was making it possible as, for example, in the case of orientable manifolds, the duality has been used to avoid explicitly working with cohomology. The cup product endows the cohomology with the ring structure which permits distinguishing between nonhomotopical spaces which homology groups do not distinguish. However, this intrinsically more difficult theory had to wait longer for computer implementations. Some of application-oriented work on computing the cohomology ring of simplicial complexes has been done by Gonzalez-Diaz and Real. We developed a cohomology ring algorithm in a dimension-independent framework of combinatorial cubical complexes.
This approach is convenient in the cup-product computation and motivated, among others, by interpreting pixels or voxels as cubes. The S-complex theory and so called co-reductions are adopted to build a cohomology ring algorithm speeding up the algebraic computations. This is joint work with M. Mrozek. The implementation of the algorithm by P. D{\l}otko is in progress.

Kerber, Michael
Alexander Duality for Functions: the Persistent Behaviour of Land and Water and Shore

This work contributes to the point calculus of persistent homology by extending Alexander duality to real-valued functions. Given a perfect Morse function $f: S^{n+1} \to [0,1]$ and a decomposition $S^{n+1} = U \cup V$ such that $M = U \cap V$ is an $n$-manifold, we prove elementary relationships between the persistence diagrams of $f$ restricted to $U$, to $V$, and to $M$.
Joint work with Herbert Edelsbrunner

Kahle, Matthew Princeton University
Higher-dimensional Expanders

Abstract: Expander graphs have found many applications in mathematics and theoretical computer science. We will discuss their generalizations to higher-dimensional simplicial complexes, providing several kinds of random polyhedra as examples. This will include joint work with Dotterrer, and also with Hoffman and Paquette.

Komendarczyk, Rafal and Jeffrey Pullen - Tulane University
Complete Coverage Probability via Homology.

We consider the issue of obtaining the probability of complete coverage for a given domain by a finite coverage process with compact convex grains. The problem is approached by by considering a random simplicial complex associated with the nerve of the coverage process. We determine distributions of random Betti numbers as well as the Euler characteristic of the nerve, which then allows us to address the complete coverage probability question. This results should have applications to e.g. sensor networks or cloud coverage.

Landi, Claudia Università di Modena e Reggio Emilia
Comparison of Persistent Homologies for Vector Functions: from continuous to discrete

The theory of multidimensional persistent homology was initially developed in the discrete setting , and involved the study of simplicial complexes filtered through an ordering of the simplices. Later, stability properties of multidimensional persistence have been proved to hold when topological spaces are filtered by continuous functions, i.e. for continuous data. This talk aims to provide a bridge between the continuous setting, where stability properties hold, and the discrete setting, where actual computations are carried out. More precisely, we develop a method to compare persistent homologies of vector functions obtained from discrete data in such a way that stability is preserved. These advances support the appropriateness of multidimensional persistent homology for shape comparison in computer vision and computer graphics applications. This is a joint work with N. Cavazza, M. Ethier, P. Frosini, and T. Kaczynski.

Matschke, Benjamin
A Parametrized Version of Gromov's Waist of the Sphere Theorem

Gromov, Memarian, and Karasev--Volovikov proved that any map f from an n-sphere to a k-manifold (n>=k) has a preimage f^{-1}(z) whose epsilon-neighborhoods are at least as large as the epsilon-neighborhoods of the equator $S^{n-k}$. We present a parametrized generalization. For the proof we introduce a Fadell-Husseini type ideal-valued index of G-bundles that is quite computable in our situation and we obtain two new parametrized Borsuk-Ulam type theorems.

Meshulam, Roy Technion Institute of Technology
Fourier transform and Homology

I'll discuss the following applications of the finite Fourier transform to combinatorial topology.
1. We study the homology of certain arithmetically constructed spaces called Sum Complexes. In particular, it is shown that sum complexes on a prime number of vertices are hypertrees, i.e. have vanishing rational homology. One ingredient in the proof is a remarkable theorem of Chebotarev concerning submatrices of the Fourier matrix. (joint work with N. Linial and M. Rosenthal)
2. Uncertainty principles roughly assert that a nonzero function and its Fourier transform cannot both be concentrated on small sets. We will point out a connection between discrete uncertainty inqualities and the topology of sum complexes.
3. We give a Fourier characterization of the top homology of balanced complexes. This leads to an extension and a short proof of a recent result of Reiner and Musiker on a topological interpretation of the coefficients of the cyclotomic polynomial.

Mileyko, Yuriy
Probability measures on the space of persistence diagrams

Persistence diagrams are topological summaries that provide useful information about the topology and geometry of data and play a crucial role in topological data analysis. However, the problem of quantifying the uncertainty, noise, and reproducibility of these topological summaries, which is a fundamental aspect of the classical data analysis, has not been well studied. In this talk, we shall show that the space of persistence diagrams has properties that allow for the definition of probability measures which support expectations, variances, percentiles and conditional probabilities. This provides a theoretical basis for a statistical treatment of persistence diagrams, for example computing sample averages and sample variances of persistence diagrams, and allows us to extend the theory of topological persistence to a much larger set of applications.

Mimram, Samuel CEA
Efficient State Space Reduction Using Trace Spaces

State-space reduction techniques, used primarily in model-checkers in order to verify programs, all rely on the idea that some actions are independent, hence could be taken in any (respective) order while put in parallel, without changing the semantics. It is thus not necessary to consider all execution paths in the interleaving semantics of a concurrent program, but rather some equivalence classes. We describe a new algorithm to compute such equivalence classes, and a representative per class, which is based on ideas originating in algebraic topology. We introduce a geometric semantics of concurrent languages, where programs are interpreted as directed topological spaces, and study its properties in order to devise an algorithm for computing dihomotopy classes of execution paths. We will also report on a preliminary implementation, showing promising results towards efficient methods to analyze concurrent programs, with better results than state of the art partial-order reduction techniques.

Morozov, Dmitriy
Witnessed k-Distance

Distance function to a compact set plays a central role in several areas of computational geometry. Methods that rely on it are robust to the perturbations of the data by the Hausdorff noise, but fail in the presence of outliers. The recently introduced \emph{distance to
a measure} offers a solution by extending the distance function framework to reasoning about the geometry of probability measures, while maintaining theoretical guarantees about the quality of the inferred information. A combinatorial explosion hinders working with distance to a measure as an ordinary power distance function. In this talk, we analyze an approximation scheme that keeps the representation linear in the size of the input, while maintaining the guarantees on the inference quality close to those for the exact but costly representation. (Joint work with Leonidas Guibas and Quentin Merigot.)

Mrozek, Marian
Towards the Understanding of the Homological Persistence of Maps.

When a topological space is known only from sampling, persistence provides a useful tool to study its homological properties. In many applications one can sample not only the space, but also a map acting on the space. The understanding of the topological features of the map is often of interest, in particular in time series analysis. We consider the concept of persistence in finite dimensional vector spaces and combine it with a graph approach to computing homology of maps in order to study the persistence of eigenspaces of maps induced in homology. This is research in progress, joint with Herbert Edelsbrunner.

Oudot, Steve
Stable Multi-Scale Signatures for Shapes using Topological Persistence

Abstract: In this talk I will introduce several families of signatures for compact Riemannian manifolds or finite metric approximations of these. Our signatures are defined as persistence diagrams of carefully chosen functions over the space, and they provide a multi-scale description of the structure of the space. Some of them are global and can be used in shape classification applications, while others have a more local nature and can be used in (partial) shape matching applications.
All our signatures are stable under small perturbations of the space in the Gromov-Hausdorff distance. I will also illustrate their practicality through a series of experiments.

Patel, Amit Rutgers University
Well Groups for Mappings to Euclidean Spaces

Given a mapping to a Euclidean space E and a point x in E, the well group quantifies the stability of the homology over x. I will introduce two definitions of a well group. The first being very intuitive but not so easy to compute. The second involves the use of intersection theory. Both definitions have similar properties of stability, but It is not clear whether the two definitions are equivalent. This raises some interesting questions.

Raussen, Martin Aalborg University
Simplicial Models for Trace Spaces

Concurrency theory in Computer Science studies the effects that arise when several processors run simultaneously sharing common resources. It attempts to advise methods to deal with the "state space explosion problem". In recent years, models with a combinatorial/topological flavor have been introduced and investigated as tools in the analysis of concurrent processes. It is a common feature of these models that an execution corresponds to a directed path (d-path), and that d-homotopies (preserving the directions) have equivalent computations as a result.
I will discuss a particular classical example of a directed space arising as a (pre-cubical set) model of a class of Higher Dimensional Automata (HDA). For such a space, I will describe a new method that determines the homotopy type of the space of traces (executions) as a prodsimplicial complex - with products of simplices as building blocks. A description of that complex opens up for (machine) calculations of homology groups and other topological invariants of the trace space. The determination of path components is particularly important for applications.
This prodsimplicial trace complex arises from a covering of a trace space by particular contractible subspaces. Nonempty (and contractible) intersections of these subspaces form a poset category with a classifying space that corresponds to a barycentric subdivision of the prodsimplicial complex.
The determination of this complex in a particular case depends on deciding whether certain subspaces of traces are empty are not. This decision relies on an algorithm detecting deadlocks and unsafe regions for these Higher Dimensional Automata by checking a bunch of inequalities.
This concept is the background for an algorithm yielding a representation of the prodsimplicial complex that has been implemented using the ALCOOL software from a lab at CEA in France. Using the outcome of the algorithm, homological invariants have been calculated using homology software by Mrozek etal.
If time permits, I will sketch a method that generalizes the main construction to arbitrary HDA taking into account processes that may branch and loop.

Robinson, Michael University of Pennsylvania
Euler integral transforms and applications

The old idea of using the combinatorial Euler characteristic as a valuation to define an integration theory found application to sensor networks in a recent paper of Baryshnikov and Ghrist. They showed that a dense network of sensors, each of which produces an integer count of nearby targets could be integrated to yield a total count of the targets within the sensor field even if the target support regions overlap. The resulting algorithm is reminiscent of signal processing techniques, though it uses integer-valued data points. Seeing as a primary tool of signal processing is the integral transform, a question is "are there integral transforms in this theory?"

It happens that many of the transforms traditionally used in harmonic analysis have natural analogs under the Euler integral. The properties of these transforms are sensitive to topological (as well as certain geometric) features in the sensor field and allow signal processing to be performed on structured, integer valued data, such as might be gathered from ad hoc networks of inexpensive sensors. For instance, the analog of the Fourier transform computes a measure of width of support for indicator functions. There are some notable challenges in this theory, some of which are present in traditional transform theory (such as the presence of sidelobes), and some which are new (such as the nonlinearity of the transform when extended to real-valued data). These challenges and some mitigation strategies will be presented as well as a showcase of the transforms and their capabilities.Reference:

Singer, Amit Princeton University
Vector Diffusion Maps and the Connection Laplacian

Abstract: Motivated by problems in structural biology, specifically cryo-electron microscopy, we introduce vector diffusion maps (VDM), a new mathematical framework for organizing and analyzing high dimensional data sets, 2D images and 3D shapes. VDM is a mathematical and algorithmic generalization of diffusion maps and other non-linear dimensionality reduction methods, such as LLE, ISOMAP and Laplacian eigenmaps. While existing methods are either directly or indirectly related to the heat kernel for functions over the data, VDM is based on the heat kernel for vector fields. VDM provides tools for organizing complex data sets, embedding them in a low dimensional space and interpolating and regressing vector fields over the data. In particular, it equips the data with a metric, which we refer to as the vector diffusion distance. In the manifold learning setup, where the data set is distributed on (or near) a low dimensional manifold $M^d$ embedded in $R^p$, we prove the relationship between VDM and the connection-Laplacian operator for vector fields over the manifold. Applications to structural biology (cryo-electron microscopy and NMR spectroscopy), computer vision and shape space analysis will be discussed. (Joint work with Hau-tieng Wu.)

Vanessa Robins, Adrian P. Sheppard, and Peter John Wood
Theory and Algorithms for Constructing Discrete Morse Complexes from Grayscale Digital Images

The rise of three-dimensional imaging technology has sharpened the need for quantitative geometric and topological analysis of 3D images. Increasingly popular tools for the topological analysis of data are Morse complexes and persistent homology. We present a homotopic algorithm for determining the Morse complex of a grayscale digital image. For two- or three-dimensional images we prove that
this algorithm constructs a discrete Morse function which has exactly the number and type of critical cells necessary to characterize the topological changes in the level sets of the image. The resulting
Morse complex is considerably simpler than the cubical complex originally used to represent the image and may be used to compute persistent homology.



Wang, Bei SCI Institute, University of Utah
Stratification Learning through Local Homology Transfer

We would like to show that point cloud data can under certain circumstances be clustered by strata in a plausible way. For our purposes, we consider a stratified space to be a collection of manifolds of different dimensions which are glued together in a locally trivial manner inside some Euclidean space. To adapt this abstract definition to the world of noise, we first define a multi-scale notion of stratified spaces, providing a stratification at different scales which are indexed by a radius parameter. We then use methods derived from kernel and cokernel persistent homology to cluster the data points into different strata. We prove a correctness guarantee for this clustering method under certain topological conditions. We then provide a probabilistic guarantee for the clustering for the point sample setting – we provide bounds on the minimum number of sample points required to state with high probability which points belong to the same strata. Finally, we give an explicit algorithm for the clustering.

Yusu, Wang
Toward understanding complex data: graph Laplacian on singular manifolds

In manifold learning, algorithms based on graph Laplacian constructed from data have received considerable attention both in practical applications and theoretical analysis. One nice property of graph Laplacian that facilitates it broad practical usage is that its construction requires only the proximity graph from input points data. Much of the existing work has been done under the assumption that the
data is sampled from a manifold without boundaries and singularities or that the functions of interest are evaluated away from such points. At the same time, it can be argued that singularities and boundaries are an important aspect of realistic data. Boundaries occur whenever the process generating data has a bounding constraint; while singularities appear when two different manifolds intersect or if a process undergoes a "phase transition", changing non-smoothly as a function of a parameter.

In this talk I will present some results from our recent study of the behavior of graph Laplacians on singular manifolds. In particular, we consider boundaries and two types of singularities: intersections, where different manifolds come together and sharp "edges", where a manifold sharply changes direction. We show that the behavior of graph Laplacian near these singularities is qualitatively different from that in the interior of the manifolds. Unlike in the interior of the domain, where graph Laplacian converges to the Laplace-Beltrami operator, near singularities graph Laplacian tends to a first-order differential operator, which exhibits different scaling behavior as a function of the kernel width. Understanding such behavior will lead to interesting applications in learning and analyzing complex data.
This is joint work with M. Belkin, Q. Que, and X. Zhou.

November 14-18, 2011
Workshop on Sphere Arrangments

Balázs, Csikós
On the Volume of the Union and Intersection of Random Balls

The generalized Kneser-Poulsen conjecture predicts that the volume of the union/intersection of some balls in the Euclidean, spherical or hyperbolic space does not decrease/increase when the balls are rearranged so that the distances between the centers increase. First we overview different weighted versions of this conjecture then turn our attention to inequalities on the expectation of the volume of the union/intersection of balls with fixed centers and random radii.

Belkin, Misha--Ohio State University
Understanding Geometric Structure of Probability Distributions

The study of Gaussian mixture distributions goes back to the late 19th century, when Pearson introduced the method of moments to analyze the statistics of a crab population. They have since become one of the most popular tools of modeling and data analysis, extensively used in speech recognition, computer vision and other fields. Yet their properties are still not well understood. Widely used algorithms, such as Expectation Maximization (EM), often fail even on simple generated data and their theoretical properties are often unclear.

In my talk I will discuss our recent results with Kaushik Sinha, which, in a certain sense, completes work on an active recent topic in theoretical computer science by establishing quite general conditions for polynomial learnability of parameters of a wide class of distributions, including Gaussian mixture models, using methods of algebraic geometry

Bezdek, Karoly - University of Calgary
On a Foam Problem and on the X-ray Conjecture

We investigate the following two problems the first of which is on sphere packings in Euclidean space and the second of which is closely connected to sphere coverings in spherical space. Thus, first
we a raise a relative of the well-known Kelvin problem that one can regard as a stronger version of the Kepler conjecture. In particular, we prove that the average surface area of any family of convex cells that tile the Euclidean 3-space with each cell containing a unit ball, is always at least 13.8564... . Second recall that a subset of the d-dimensional Euclidean space having nonempty interior is called a
spindle convex body if it is the intersection of (finitely or infinitely many) congruent d-dimensional closed balls. The spindle convex body is called a
``fat'' one, if it contains the centers of its generating balls. We outline a proof of the X-ray Conjecture for fat spindle convex bodies in dimensions 3, 4, 5, and 6 as well as in dimensions greater than or equal to 15.

Fasy, Brittany Terese
Ghosts in Gaussian Mixture Models

The sum of n isotropic Gaussian kernels can have more than n modes. We give a thorough analysis of the sum of n Gaussians centered at the vertices of the standard (n-1)-simplex.

Fejus Toth, Gabor - Alfred Renyi Institute of Mathematics
Shortest Path Avoiding Balls

Given a packing of open balls and two points outside the balls at distance d from one another, nd the shortest path connecting the two points and avoiding the balls. We give an upper bound for the length of the shortest path showing that the he detour we have to make in order to cover a given distance d from one point to another one avoiding the members of a packing of balls with bounded radii in En approaches zero with the dimension. We also mention some open problems.

Hardin, Douglas - Vanderbilt University
Discretizing Compact Manifolds with Minimum Energy.

The problem of finding configurations of points that are “optimally-distributed” on a set appears in a number of guises including best-packing problems, coding theory, geometrical modeling, statistical sampling, radial basis approximation and golf-ball design (i.e., where to put the dimples). This talk will focus on classical and recent results concerning asymptotic geometrical properties of N-point configurations on a compact metric set A interacting through a weighted inverse power law for large values of N. This is joint work with S. Borodachov, E. Saff and T. Whitehouse.

Haucourt, Emmanuel
Unique Decomposition and its Application to Concurrency Theory

The PV-Language was introduced by E.W. Dijkstra as a toy example for the study of Concurrency - a theoretical branch of Computer Science. There is a natural way to associate each PV-program with a directed topological space. The shapes modeling PV-programs actually lie in a family which enjoys a free commutative monoid structure. From a practical point of view, a PV-program is made of several processes running together and sharing the same pool of resources. The from the decomposition of its modeling shape we can gather processes into groups running independently from each each other. Moreover, the component category invariant turns any model of PV program into a finite nonempty connected loop-free category. Such categories also admit a free commutative monoid structure. We conjecture a relation between the decomposition of a shape and the decomposition of its component category.

Musin, Oleg University of Texas at Brownsville (pls. assign talk November 14-17)
Packing of congruent spheres on a sphere.

We consider several classical and new methods for upper bounds on densest packing of congruent spheres on a sphere:
(1) Fejes Toth's bound of circles packings (1943). Coxeter (1963) extended this bound for higher dimensions.
(2) Distance and irreducible graphs of circles packings [Schutte and van der Waerden (1951), Leech (1956), Danzer (1963)].
(3) Linear programming and SDP;
(4) Combination of (2) and (3).

Pach, Janos EPFL and NYU
Heavily Covered Points in Geometric Arrangements

According to the Boros-F\"uredi-B\'ar\'any theorem, for any system of $n$ points in Euclidean $d$-space, there is a point contained in at least a constant fraction of all simplices generated by them. We discuss some related problems for geometric arrangements. One of our tools will be the following: Let $\alpha>0$, let $H_1,\ldots,H_m$ be finite families of semi-algebraic sets of constant
description complexity, and let $R$ be a fixed semi-algebraic $m$-ary relation on $H_1\times\cdots\times H_m$ such that the number of $m$-tuples that are related (resp. unrelated) with respect to $R$ is at least $\alpha\prod_{i=1}^m|H_i|$. Then there exists a constant $c>0$, which depends on $\alpha, m$ and on the maximum description complexity of the sets in $H_i\; (1\le i\le m)$ and $R$, and exist subfamilies $H^*_i\subseteq H_i$ with $|H^*_i| \geq c'|H_i|\; (1\le i\le m)$ such that $H^*_1\times\cdots\times H^*_m\subset R$ (resp. $H^*_1\times\cdots\times H^*_m\cap R=\emptyset$). (Joint work with Jacob Fox, Mikhail Gromov, Vincent Lafforgue \and Assaf Naor.)

Stephenson, Ken University of Tennessee
Circle packings and circle arrangements: searching for common ground

Circle packings are configurations of circles having prescribed patterns of tangency. They are not traditional 2D sphere arrangements because it is their tangency "patterns" that are specified, while the individual circle sizes are flexible. However, there is an "edge-flipping" operation on combinatorics which leads to interesting dynamics in circle packing. Experiments suggest that some common ground may emerge with the spherical arrangement community--- and there may be a few practical applications as well.

Toth, Csaba University of Calgary
On the Average Distance from the Fermat-Weber Center of a Planar Convex Body

The Fermat–Weber center of a planar body Q is a point in the plane from which the average distance to the points in Q is minimal. We first show that for any convex body Q in the plane, the average distance from the Fermat–Weber center of Q to the points in Q is larger than Delta(Q)/6, where Delta(Q) is the diameter of Q. From the other direction, we prove that the same average distance is at most 0.3490 Delta(Q). The new bound brings us closer to the conjectured value of Delta(Q)/3. We also confirm the upper bound conjecture for centrally symmetric planar convex bodies.
(Joint work with Adrian Dumitrescu and Minghui Jiang)

Wang, Bei SCI Institute, University of Utah
Adaptive Sampling with Topological Scores

Understanding and describing expensive black box functions such as physical simulations is a common problem in many application areas. One example is the recent interest in uncertainty quantification with the goal of discovering the relationship between a potentially large number of input parameters and the output of a simulation. Typically, the simulation of interest is expensive to evaluate and thus the sampling of the parameter space is necessarily small. As a result choosing a “good” set of samples at which to evaluate is crucial to glean as much information as possible from the fewest samples. While space-filling sampling designs such as Latin Hypercubes provide a good initial cover of the entire domain more detailed studies typically rely on adaptive sampling. The core of most adaptive sampling methods is the scoring function which, given an initial set of training points ranks a large set of candiate points to determine the most valuable one for evaluation. Traditional scoring functions are based on well know geometric metrics such as distance in function space. Instead, we propose topology based techniques that aim to recover the global structure of the simulation response. In particular, we propose three new topological scoring functions based on persistent homology and demonstrate that especially for complicated functions and higher dimensions these outperform traditional techniques.

Womersley, Rob--University of New South Wales
Spherical designs and approximate spherical designs

Spherical t-designs are sets of points on the unit sphere such that the equal weight cubature rule at these points is exact for all spherical polynomials of degrees at most t. As such they can be
regarded as a quasi-Monte Carlo rule for the sphere. Most attention has been focussed on the minimum numbers of points N needed for a spherical t-design.
This talk will focus on the two-sphere and calculation of spherical t-designs with $N = t^2 / 2 + O(t)$ and t up to degree 221, their geometrical properties, such as mesh norm, separation, (spherical cap) discrepancy, worst case error and energy. To enable fast generation of point sets we also consider approximate spherical designs.

back to top