Triangulation and Random Incremental Paths
TRIP is an associated
team funded by
The project started in February 2018.
We will investigate various problems linked to routing in triangulations. The main objective will be to design various routing strategies that only use local information and produce paths of good quality. By good quality, we mean that the length of the path should not exceed the length of the shortest path by more than a constant factor. Such routing strategies are known as competitive routing strategies. We intend to design and analyze these routing strategies under different kinds of hypotheses on the data distribution. We highlight below in more detail some of the specific problems that will be addressed:
- Stretch factor of the Delaunay triangulation in 3D.
- Theta-graphs and Yao-graphs.
- Smoothed analysis of a walk in Delaunay triangulation.
- Walking in/on surfaces.
- Non-Euclidean issues
- French participants at Inria Gamble team
- Canadian participants at CGLab
Improved routing on the Delaunay triangulation.
Nicolas Bonichon, Prosenjit Bose, Jean-Lou de Carufel, Vincent Despré, Darryl Hill, Michiel Smid.
ESA 2018 - 26th Annual European Symposium on Algorithms, Aug 2018, Helsinki, Finland.
Expected complexity of routing in Θ6 and half-Θ6 graphs.
Prosenjit Bose, Jean-Lou de Carufel, Olivier Devillers.
2019. hal arXiv:1910.14289.
To appear JoCG 2020.
Routing in triangulations on surfaces.
Prosenjit Bose, Jean-Lou de Carufel, Olivier Devillers, Maia Fraser, Monique Teillaud.
- May 23 - June 25: Charles Duménil visited Carleton University.
- October 18 - 26: Jit Bose and Jean-Lou de Carufel visited INRIA in Nancy
- November 12 - 23 : Olivier Devillers visited Carleton University.