Workshop on Stochastic Geometry and Random Generation

Workshop description - Organizers - Program - Abstracts - Support --- CG Week 2015

Description

Probabilistic methods are ubiquitous in computer science and computational geometry is no exception: from randomized algorithms, average-case complexity analysis of algorithms, to Erdós' probabilistic lens in discrete geometry, probabilistic methods have had a major impact on the field.

Most often, probabilistic methods are used in computational geometry by computational geometers themselves. There are, however, entire areas dedicated to the understanding of the properties of random geometric objects (stochastic geometry) or random generation mechanisms (analytic combinatorics).

The proposed workshop aims at stimulating new interactions between these areas and the international community of discrete and computational geometers.

Organizers

Olivier Devillers and Xavier Goaoc

Tentative program

Thursday, June 25: 14:00-15:35 and 16:00-17:30
14:00-14:05 Welcome - slides
14:05-14:50 Pierre Calka (Université de Rouen) Introduction to several models from stochastic geometry. - slides
14:50-15:35 Philippe Duchon (Université Bordeaux) Introduction to the random generation of discrete structures - slides
15:35-16:00 Coffee Break
16:00-16:45 Matthias Schulte (Karlsruher Institut für Technologie) Central limit theorems for random tessellations and random graphs. - slides
16:45-17:30 Sergei Zuyev (Chalmers University of Technology, Gothenburg) Generalised Eden growth model and random planar trees - slides

Abstracts

Introduction to several models from stochastic geometry.

Pierre Calka (Université de Rouen)
Stochastic geometry can be described as the study of Euclidean objects with a random behaviour. First problems in geometric probability were presented as recreational mathematics but the domain has substantially grown for 50 years, in particular because of its many applications including experimental science and especially analysis of geometric algorithms.
The talk will be centered on the description of several classical models from stochastic geometry: random tessellations and in particular the Poisson-Voronoi and Poisson-Delaunay tessellations, random geometric graphs, random polytopes constructed as convex hulls of a random point set, etc. We will survey the basic properties of each of them and focus in particular on some of their asymptotic properties which can provide valuable information in the context of computational geometry.

Introduction to the random generation of discrete structures

Philippe Duchon (Université Bordeaux )
In many situations, one is able to define "natural" probability distributions on some set of discrete structures that one wants to study and/or simulate. This of course includes uniform distributions on finite sets, but in many cases the distribution is defined through some invariance property. Classical examples with a geometric flavor include tilings. The talk will focus on techniques used to algorithmically simulate, exactly on approximately, such a probability distribution - that is, sample discrete structures according to some previously defined probability distribution on a finite (but large) or infinite set.

Central limit theorems for random tessellations and random graphs.

Matthias Schulte (Karlsruher Institut für Technologie)
The topic of this talk are random tessellations and random graphs like Poisson-Voronoi tessellations and the nearest neighbour graph, which play an important role in stochastic geometry. Since the exact behaviour of related quantities as the total edge length, for example, is often very hard to determine, one is interested in the asymptotic behaviour as the size of the underlying system gets large. For this situation central limit theorems are presented that allow to approximate random variables by standard Gaussian random variables if the size of the system is sufficiently large. All considered problems have in common that they are driven by an underlying Poisson point process. The central limit theorems can be deduced via general normal approximation results for random variables depending on Poisson point processes.

Generalised Eden growth model and random planar trees

Sergei Zuyev (Chalmers University of Technology, Gothenburg)
In a classical Eden growth model, a crystal on a grid extends to nearby nodes with the rate proportional to the number of already crystallised neighbours. This model is equivalent to first-passage percolation with exponential passage time. An extension of this model is to allow a general weight for different number of crystallised neighbours. Classical subadditivity arguments allow establishing existence of a limiting shape for the most natural case of monotone rates: the more neighbours are crystallised, the sooner a boundary node crystallises too. However, a real challenge represent non-monotone rates where all the classical approaches to establishing the shape result fail. Computer simulations suggest that even in this case a limiting shape does exist. We present partial results for such models and discuss some of their intriguing features: existence of holes, the exponential bound of their size and possible long-range structural dependence.

Support

ANR Presage