december 8

10:00 - 10:30

Welcome and coffee

10:30 - 12:00

Presentations

10:30 - 11:15

Curvature and combinatorics of triangulations
John Sullivan (Technische Universität Berlin)

There is a rich interplay between combinatorial and differential geometry. For 2-manifolds, the Gauss-Bonnet theorem gives a clear connection between combinatorics (say of a triangulation) and curvature/topology. This picture also has new applications giving a more detailed classification of surface triangulations. We will also examine to what extent something similar can be done for 3-manifolds.

slides.

11:15 - 12:00

The Poincaré dodecahedral space
Gert Vegter (Johann Bernoulli Institute for Mathematics and Computer Science, Groningen), Rien van de Weijgaert (Kapteyn Institute, Groningen)

For ages people have wondered what the shape of the universe could be. Whereas the geometry of the Universe has, by now, been established by Einstein's theory of relativity, this theory does not determine the exact 3-manifold that is physical space. Enquiry into the global shape of the Universe, more specifically its topology, has been ongoing for about a century now, but recently some new evidence emerged. In 2003, data from the WMAP experiment led Jean-Pierre Luminet to propose a multiconnected spherical space model called the Poincaré dodecahedral space (PDS). We discuss the meaning of this claim from both a mathematical and a physical perspective. Specifically, we will discuss the relevant physical and cosmological evidence on the topological structure of the Universe and investigate whether there is any possibility for a PDS. Also, the PDS will be shown to be a spherical space with a dodecahedral fundamental domain.
paper.

slides.

12:00 - 14:00

Lunch

14:00 - 15:30

Presentations

14:00 - 14:45

Shortest cut graph of a surface with prescribed vertex set
Éric Colin de Verdière (ENS)

A cut graph of a surface is an embedded graph that splits the surface into a topological disk. Erickson and Whittlesey [SODA 2005] found a very nice greedy algorithm to compute the shortest one-vertex cut graph of a combinatorial surface. This talk will show how their algorithm extends to the computation of a shortest cut graph with a given vertex set. Moreover, a simpler proof will be given, also revealing that the algorithm actually computes a minimum-weight basis of some matroid.
paper .

slides.

14:45 - 15:30

Sculpting shapes of arbitrary topology in real-time
Lucian Stanculescu (Liris)

I will present a method for sculpting a watertight and manifold triangular mesh which can accommodate topology changes. The key idea is to maintain a homogeneous sampling of the surface throughout the deformation, thus allowing the detection of topology changes from simple collisions between spheres. The example image shows an object sculpted from a sphere.

slides.

15:30 - 16:00

Coffee Break

16:00 - 17:30

Presentations

16:00 - 16:45

Linear Cameras
Jean Ponce (ENS)

I will address in this talk the problem of characterizing a general class of cameras under reasonable, "linear" assumptions. Concretely, I will use the formalism and terminology of classical projective geometry to model cameras by two-parameter linear families of straight lines---that is, degenerate reguli (rank-3 families) and non-degenerate linear congruences (rank-4 families). This model captures both the general linear cameras of Yu and McMillan and the linear oblique cameras of Pajdla. I will show that it affords a simple classification of all possible geometric camera configurations. From an analytical viewpoint, our model also provides a simple and unified methodology for deriving general formulas for projection and inverse projection, triangulation, and binocular and trinocular geometry. In addition, it is possible to generalize Pajdla's model of oblique cameras by certain projective maps to all linear cameras, and introduce a natural notion of intrinsic parameters for these cameras, further simplifying the corresponding single- and multi-view formulas. I will conclude by showing a prototype of a parabolic camera. Joint work with Guillaume Batog and Xavier Goaoc at INRIA Nancy Grand Est.

16:45 - 17:30

Balls, sticks, triangles and molecules
Frédéric Cazals (INRIA)

``Do you think that you will succeed in modeling molecules using balls, sticks and triangles?'' This is the admittedly provocative question I was asked by a molecular biologist during a workshop at the NIH in Bethesda in 2008, and this talk will provide two illustrations of geometric constructions indeed improving our understanding of correlations between biophysical and geometric (structural) properties of macro-molecules. In the first part, we shall consider the problem of describing and comparing protein interfaces. We shall see that a sprinkle of affine Voronoi diagrams mixed with elementary ideas form Morse theory and baked with graph matching algorithms allows one to precisely investigate macro-molecular recognition through the atomic-modeling of interfaces. In the second one, we shall switch scales and consider the biggest protein assembly known to date in Eukaryotic cells, namely the Nuclear Pore Complex. I shall explain how the alpha-shape associated to a compoundly-weighted Voronoi diagram allows one to make a quantitative assessment of qualitative models of the NPC proposed by structural biologists.

slides.

december 9

09:30 - 10:15

Presentations

09:30 - 10:15

Asymptotic properties of the typical Poisson-Voronoi cell and other random polytopes
Pierre Calka (Université de Rouen)

Abstract. In this talk, we define several models of random polytopes in the Euclidean space. Examples include the convex hull of independent and uniformly distributed points in a fixed convex set and the typical Poisson-Voronoi cell (chosen uniformly among all cells from the Voronoi tessellation generated by a homogeneous Poisson point process). First we show distributional properties of some of their characteristics. Then we focus on the description of their asymptotic shape. In particular, we develop a local scaling theory for the boundary itself of the random polytope, seen as a random process. We obtain variance asymptotics, invariance principles and extreme value results.

slides.

10:15 - 10:45

Coffee Break

10:45 - 12:15

Presentations

10:45 - 11:30

Smooth analysis of the convex hull of points
Olivier Devillers (INRIA)

Assume that Y is a noisy version of a point set X in convex position. How many vertices does the convex hull of Y have, that is, what is the number of extreme points of Y?
We consider the case where X is an (ε,κ)-sample of a sphere in R^d and the noise is random and uniform: Y is obtained by replacing each point x in X by a point chosen uniformly at random in some region S(x) of size a around x. We give upper and lower bounds on the expected number of extreme points in Y when S(x) is a ball (in arbitrary dimension) or an axis-parallel square (in the plane). Our bounds depend on the size n of X and a, and are tight up to a polylogarithmic factor. These results naturally extend in various directions (more general point sets, other regions S(x)...).
We also present experimental results, showing that our bounds for random noise provide good estimators of the behavior of snap-rounding, that is when Y is obtained by rounding each point of X to the nearest point on a grid of step a. We describe how the technique generalizes to obtain (up to polylog factor) tight upper bound on size of the 3D Delaunay triangulation when the input points are randomly perturbed.
paper .

slides.

11:30 - 12:15

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
Menelaos Karavelas (University of Crete)

Given a set Σ of spheres in E^d, with d ≥ 3 and d odd, having a fixed number of m distinct radii r₁,r₂,...,r_m, we show that the worst-case combinatorial complexity of the convex hull CH_d(Σ) of Σ is Θ(∑_{1≤i ≠ j ≤m} n_in_j^floor(d/2)), where n_i is the number of spheres in Σ with radius r_i. Our bound refines the currently best upper bound on the worst-case combinatorial complexity of CH_d(Σ) for all odd d ≥ 3. To prove the lower bound, we construct a set of n₁+n₂ spheres in E^d, with d ≥ 3 odd, where n_i spheres have radius r_i, i=1,2, and r₂ ≠ r₁, such that their convex hull has combinatorial complexity Ω(n₁n₂^floor(d/2) + n₂n₁^floor(d/2) ) . Our construction is then generalized to the case where the spheres have m distinct radii. For the upper bound, we reduce the sphere convex hull problem to the problem of computing the worst-case combinatorial complexity of the convex hull of a set of m d-dimensional convex polytopes lying on m parallel hyperplanes in E^d+1, where d ≥ 3 odd, a problem which is of independent interest. More precisely, we show that the worst-case combinatorial complexity of the convex hull of a set P₁,P₂,...,P_m of m d-dimensional convex polytopes lying on m parallel hyperplanes of E^d+1 is O(∑_{1≤i≠j≤m}n_in_j ^floor(d/2)), where n_i is the number of vertices of P_i. This bound is an improvement over the worst-case bound on the combinatorial complexity of the convex hull of a point set where we impose no restriction on the points' configuration; using the lower bound construction for the sphere convex hull problem, it is also shown to be tight for all odd d ≥ 3. Finally, we: (1) briefly discuss how to compute convex hulls of spheres with a fixed number of distinct radii, or convex hulls of a fixed number of polytopes lying on parallel hyperplanes; (2) how our tight bounds for the parallel polytope convex hull problem, yield tight bounds on the combinatorial complexity of the Minkowski sum of two convex polytopes in E^d; and (3) state some open problems and directions for future work.

slides.

12:15 - 14:00

Lunch

14:00 - 15:30

Presentations

14:00 - 14:45

Exact Voronoi Diagram of Arbitrary Lines in Space - with fast point location
Michael Hemmer (Tel Aviv University)

For a set of objects the Voronoi Diagram (VD) is the partition of space into cells, where each cell is defined as the set of all points that are closer to a particular object than to all other objects. The VD is a fundamental data structure in Computational Geometry. We introduce a new, efficient, and complete algorithm, and its exact implementation, to compute the Voronoi diagram of lines in three-dimensions. This is a major milestone towards the robust construction of the Voronoi diagram of polyhedra. Following the exact geometric computation paradigm, it is guaranteed that we always computes the mathematically correct result. The algorithm is complete in the sense that it can handle all configurations, in particular all degenerate ones. The algorithm requires O(n³+ε) time and space, where n is the number of lines. The Voronoi diagram is represented by a data structure that permits answering point location queries in O(log²n) expected time. The implementation employs the CGAL packages for constructing arrangements and lower envelopes on parametric surfaces together with advanced algebraic tools. The talk will also report on recent preliminary work extending the algorithm towards polyhedra.

14:45 - 15:30

3D real time visualisation in a rich internet application
Fabien Cellier (Liris)

The GIS softwares are commonly used in cartography, urban planning and land surveying. As in many other areas of computer science, new applications embedded in web browsers have emerged recently and we now have 3d clients for the web that can display models at resolutions superior to one triangle per pixel. This talk will present the latest advances in visualization of digital terrain model and how these algorithms can be adapted to the context of new browsing devices (typically smartphones) and new CPU/GPU hardware architectures.

slides.

15:30 - 16:00

Coffee Break

16:00 - 16:45

Presentations

16:00 - 16:45

Persistent Alpha Shape Topology of the Cosmic Web
Rien van de Weijgaert (Kapteyn Institute, Groningen)

Over the past decades a clear paradigm has emerged as large redshift surveys opened the window onto the distribution of matter in our Local Universe: galaxies, intergalactic gas and dark matter exist in a wispy weblike spatial arrangement consisting of dense compact clusters, elongated filaments, and sheetlike walls, amidst large near-empty void regions. The Cosmic Web is the fundamental spatial organization of matter on scales of a few up to a hundred Megaparsec, scales at which the Universe still resides in a state of moderate dynamical evolution. To understand the topological structure of the Cosmic Web, we study the alpha shapes defined by the Megaparsec Cosmic Web. Alphashapes were introduced by Edelsbrunner to formalize the concept of "shape" for a spatial point dataset. A large value of alpha corresponds to the convex hull of the dataset, while as alpha shrinks the alphashape assumes cavities which may join to form tunnels and voids. A related concept is the alpha complex, which for each alpha is the corresponding subcomplex of the three-dimensional Delaunay tessellation. We have studied the alpha complex of the cosmic weblike point patterns, in order to assess the signature of filaments, walls and voids. The topology of the corresponding alpha complexes is characterized by Betti numbers. The physical interpretation is determined from a range of cellular point distributions. The findings from the Voronoi clustering models is used to analyze the outcome of cosmological N-body simulations and the SDSS galaxy redshift survey.

december 10

9:30 - 11:45

PhD defense
Triangulating Point Sets in Orbit Spaces
Manuel Caroli


Referees: Kurt Mehlhorn and John Sullivan
Defense Committee: Éric Colin de Verdière, Menelaos Karavelas, Jean-Marc Schlenker, John Sullivan, Monique Teillaud (advisor), Gert Vegter, and Andreas Fabri (invited).

Abstract:
In this work we discuss triangulations of spaces of different topology defined by given point sets. We propose a general definition, valid for different classes of spaces, and an algorithm to compute Delaunay triangulations of these spaces. We provide an implementation for the specific case of the three-dimensional flat torus.
The work is originally motivated by the need for software computing three-dimensional periodic Delaunay triangulations in numerous domains including astronomy, material engineering, biomedical computing, fluid dynamics etc. Periodic triangulations can be understood as triangulations of the flat torus. We provide a definition and develop an efficient incremental algorithm to compute Delaunay triangulations of the flat torus. The algorithm is a modification of the incremental algorithm for computing Delaunay triangulations in E^d. Unlike previous work on periodic triangulations we avoid maintaining several periodic copies of the input point set whenever possible. Also the output of our algorithm is guaranteed to always be a triangulation of the flat torus.
We provide an implementation of our algorithm that has been made available to a broad public as a part of the Computational Geometry Algorithms Library CGAL (www.cgal.org).
We generalize the work to a more general class of flat quotient spaces as well as quotient spaces of constant positive curvature. We furthermore consider the double torus as a representative of the much richer class of quotient spaces of constant negative curvature.