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

Metadatos

Licencia de uso del documento

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]

Idioma

Communication dans un congrès

Este ítem está publicado en

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

Resumen en inglés

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.< Leer menos

URI

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

Proyecto ANR

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

Orígen

Importado de Hal

Centros de investigación

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