Analyse et Simulation Probabilistes d'Algorithmes Géométriques
Analysis and Probabilistic Simulations of Geometric Algorithms
ASPAG projet is funded by ANR undered number ANR-17-CE40-0017
The project started January 1st 2018 and will finish in december 2021.
The analysis and processing of geometric data has become routine in a variety of human activities ranging from computer-aided design in manufacturing to the tracking of animal trajectories in ecology or geographic information systems in GPS navigation devices. Geometric algorithms and probabilistic geometric models are crucial to the treatment of all this geometric data, yet the current available knowledge is in various ways much too limited: many models are far from matching real data, and the analyses are not always relevant in practical contexts. One of the reasons for this state of affairs is that the breadth of expertise required is spread among different scientific communities (computational geometry, analysis of algorithms and stochastic geometry) that historically had very little interaction. The Aspag project brings together experts of these communities to address the problem of geometric data. We will more specifically work on the following three interdependent directions.
(1) Dependent point sets: One of the main issues of most models is the core assumption that the data points are independent and follow the same underlying distribution. Although this may be relevant in some contexts, the independence assumption is too strong for many applications.
(2) Simulation of geometric structures: The phenomena studied in (1) involve intricate random geometric structures subject to new models or constraints. A natural first step would be to build up our understanding and identify plausible conjectures through simulation. Perhaps surprisingly, the tools for an effective simulation of such complex geometric systems still need to be developed.
(3) Understanding geometric algorithms: the analysis of algorithm is an essential step in assessing the strengths and weaknesses of algorithmic principles, and is crucial to guide the choices made when designing a complex data processing pipeline. Any analysis must strike a balance between realism and tractability; the current analyses of many geometric algorithms are notoriously unrealistic.
Aside from the purely scientific objectives, one of the main goals of Aspag is to bring the communities closer in the long term. As a consequence, the funding of the project is crucial to ensure that the members of the consortium will be able to interact on a very regular basis, a necessary condition for significant progress on the above challenges.
- First meeting January 18-19 2018, Paris,
Jussieu, aile 16-26, salle 113 (1er étage), au LIP6;
- January 18, 10h-12h
- 10h00 Opening (Olivier Devillers)
- 10h30 Task 1, Dependent point sets, review of open problems (Pierre Calka)
- 11h00 Task 2, Simulation of geometric structures, review of open problems (Philippe Duchon)
- 11h30 Task 3, Understanding geometric algorithms, review of open problems (Nicolas Broutin)
- January 18, 14h-17h00
Séminaire Francilien de Géométrie Algorithmique et Combinatoire:
séance géométrie et proba à l'IHP
featuring Marie Albenque (LIX) and Philippe Chassaing (IECL [ASPAG]).
- January 19, 9h30-12h30
- 09h30 L. Decreusefond, Repulsive and attractive processes.
- 10h30 M. Fradelizi, Convergence of Minkowski sums of compact sets to their convex hull
- 11h00 break
- 11h15 Aspag Business meeting, origanization issues. topics
- January 19, 14h-16h30
- 14h00 O. Devillers, Upper bound on walking strategies in Poisson Delaunay triangulation.
- 14h30 N. Chenavier, Lower bound on the shortest path in Poisson Delaunay triangulation.
- 15h00 Discussion on Aspag scientific topics.
- Prospective workshop, April 8-12 2018 in Arcachon.
Despite the trains on strike, we succeed to gather about 20
participants, including 4 non Aspag guests.
Amongst the 12 problems posed at the open session problem, we made
significant progress concerning about half of them which
should be substantiated by some publications in the coming months.
- Second meeting September 25-26 2018, Paris,
Telecom, salle F900, Participants
- September 25, 10h-18h
- 10:15 Opening (Olivier Devillers)
- 10:30 Maximal degree of a vertex in Poisson-Delaunay triangulations. (Nicolas Chenavier)
- 11:15 The Directed Spanning Forest converges to the Brownian Web. (David Coupier)
- 12:00 Lunch
- 14:00 Simulation du Ginibre (Guillaume Moroz)
- 14:45 Une application de complexes simpliciaux aléatoires (Xavier Goaoc)
- 15:30 Break
- 16:00 Aspag Business meeting, origanization issues. topics
- 16:45 Working groups
- Markov chain on Delaunay (Laurent, Olivier, Marc G, Guillaume, David, Arnaud)
- Simulation of determinantal processes (Laurent, Guillaume)
- Random flag geometries (Vincent D, Philippe C)
- Voronoi fractals (Pierre, Yann, Olivier, Phiilippe D)
- 19:30 Restau
- September 26, 9h30-16h
- 9:30 Processus alpha-stable (Aurélien Vasseur)
- 10:15 Break
- 10:45 Partitions récursives de différents domaines et leurs propriétés limites (Nicolas Broutin)
- 11:30 Marches persistantes multi-dimensionnelles (Arnaud Rousselle)
- 12:15 Lunch
- 14h: Working groups
- Butterfly and order types (Philippe D, Xavier, Olivier, Matthieu, Marc G)
- Random polytopes and floating bodies (Alfredo, Matthieu, Xavier)
- Roots pf polynomial systems (Guillaume, Laurent, Matthieu, Nathanael, Vincent D, Pierre)
- Min angle routing in Delaunay (Olivier, Nicolas B, Charles, Marc P, Marc G, Philippe D)
The following visits between project participants have been organized:
- Xavier Goaoc visits Marne la Vallée , September 2018.
- Xavier Goaoc visits Marne la Vallée , November 9th, 2018.