Triangulation and Random Incremental Paths
TRIP is an associated
team funded by
INRIA
The project started in February 2018.
Abstract
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
Participants
- French participants at Inria Gamble team
- Canadian participants at CGLab
Joint Publications
-
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.
doi: 10.4230/LIPIcs.ESA.2018.22
-
Expected complexity of routing in Θ6 and half-Θ6 graphs.
Prosenjit Bose, Jean-Lou de Carufel, Olivier Devillers.
Journal of Computational Geometry, 2020, 11 (1), pp.212 - 234.
-
Routing in triangulations on surfaces.
Prosenjit Bose, Jean-Lou de Carufel, Olivier Devillers, Maia Fraser, Monique Teillaud.
In preparation
Visits
- 2018
- 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.
- 2019
- 2020