Triangulation and Random Incremental Paths

Abstract Participants Publications Visits

TRIP is an associated team funded by INRIA
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:



Not yet