Probabilistic methods for efficient geometric structures and algorithms – PRESAGE

We organize 2-days meetings (2-3 times a year) where we give talks to bridge the cultural gap between the communities. We also organize two 1-week workshops (in the 1st and 2nd years) gathering all participants for active discussion of research problems. Last, we co-advise a PhD student and a post-doc.

- New, simpler or more precise, complexity analyses of geometric structures (polytopes, Delaunay triangulations, silhouette) induced by random point processes.
- New algorithm for marching in triangulations. This is the first ``non-Markovian'' algorithm for which the expected complexity on Poisson point processes can be analyzed.
- Analysis of random series built from Voronoi tesselations.
- Analysis of recurrence/transience of random walks on geometric graphs.
- Development of a software for the efficient analysis of statistical properties of random point sets.

The outcomes of the project will be theoretical results and new insights in the working of geometric algorithms.

The outcome of this project take the form of publications (in international conferences or peer-reviewed journals), of training of young researchers (Phd students and post-docs) in the techniques of both fields, of development of software packages for the CGAL library.

BACKGROUND.
Probabilistic methods are ubiquitous in computer science and computational geometry, the area that specializes in the design of algorithms for problems of geometric nature, is no exception: from randomized algorithms, average-case complexity analysis of algorithms (or, its recent refinement, smoothed complexity analysis) to Erdos' 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. This often requires a good understanding of the properties of random geometric objects, an understanding that is the focus of the field of probabilistic geometry in mathematics. Surprisingly, the two fields have had very little interaction in the past.

OVERVIEW.
This project brings together computational and probabilistic geometers to tackle new probabilistic geometry problems arising from the design and analysis of geometric algorithms and data structures. This will lead to new research directions in probabilistic geometry as well as a better understanding of geometric algorithms and data-structures. We will focus on properties of discrete structures induced by or underlying random continuous geometric objects and consider three types of questions.

* What does a random geometric structure (convex hulls, tesselations, visibility) look like? Such questions have been investigated in the past in computational geometry and probabilistic geometry, but from different perspectives: computational geometers obtained simple asymptotic bounds on very specific substructures whereas probabilistic geometers obtained probability law estimates for global properties. Our goal is to combine these two viewpoints and obtain strong results on specific aspects of random geometric structures that are relevant to algorithmic applications.

* How to analyze and optimize the behaviour of classical algorithms on "usual" inputs? Worst-case analysis is usually only a crude estimate of how geometric algorithms perform on real-life data. Our goal is to consider certain classical algorithms (typically, Delaunay triangulations) that leave room for fine-tuning (parameters, choice of methods), analyze how they perform for randomly distributed random input and optimize them for such input. The input distribution may range from classical random points in space to random perturbations of specific configurations (smoothed analysis), including intermediate models such as points randomly distributed on lower-dimensional manifolds, etc...

* How can we generate randomly "interesting" geometric structures? Geometric questions are usually phrased over continuous, geometric objects but often only depend on some underlying discrete structure; examples include finite point sets in the plane (and their order-type) or polynomial systems (and their Newton polytopes or their Hilbert series). When using randomness to explore configuration spaces to search for a "reasonably good" solution to a problem or a counter-example to a conjecture, the challenge is to generate continuous geometric objects with diverse underlying discrete structures. A natural starting point is to understand the distributions of discrete structures induced by "natural" distributions of continuous geometric objects.


ORGANIZATION.
There are three partners, two teams for computational geometers (Sophia-Antipolis and Nancy) and one team of probabilistic geometers (Rouen-Poitiers-Orléans).

An important aspect of this project is its interdisciplinarity, and we will ensure that a real collaboration takes place by:
* organizing one-week workshops in the two first years. Each workshop will gather from 10 to 20 people, students and established researchers,  for a week of active discussions of research problems.
* funding a PhD thesis co-advised by a computer scientist (O. Devillers) and a mathematician (P. Calka).