BONICHON, Nicolas; GAVOILLE, Cyril; HANUSSE, Nicolas; PERKOVIC, Ljubomir

Métadonnées

Licence d’utilisation du document

BONICHON, Nicolas
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Institut universitaire de France [IUF]

HANUSSE, Nicolas
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

Langue

Communication dans un congrès

Ce document a été publié dans

20th Annual European Symposium on Algorithms (ESA), 20th Annual European Symposium on Algorithms (ESA), 20th Annual European Symposium on Algorithms (ESA), 2012-09, Ljubljana. 2012-09, vol. 7501 of Lecture Notes in Computer Science, p. 205-216

Résumé en anglais

In this paper we determine the stretch factor of L1-Delaunay and L∞-Delaunay triangulations, and we show that it is equal to √(4 + 2√2) ≈ 2.61. Between any two points x, y of such triangulations, we construct a path whose length is no more than √(4 + 2√2) times the Euclidean distance between x and y, and this bound is the best possible. This definitively improves the 25-year old bound of triangulations of √10 by Chew (SoCG '86). This is the first time the stretch factor of the Lp-Delaunay for any real p ≥ 1, is determined exactly.< Réduire

URI

https://oskar-bordeaux.fr/handle/20.500.12278/197876

Project ANR

Calculabilité et complexité en distribué - ANR-11-BS02-0014

Origine

Importé de hal

Unités de recherche

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800