The Stretch Factor of ${L}_1$- and ${L}_\infty$-{D}elaunay Triangulations
BONICHON, Nicolas
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
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]
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]
See more >
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
BONICHON, Nicolas
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
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]
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]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
PERKOVIC, Ljubomir
School of Computer Science, Telecommunications, and Information Systems [DePaul] [CTI]
School of Computing [DePaul] [SOC]
< Reduce
School of Computer Science, Telecommunications, and Information Systems [DePaul] [CTI]
School of Computing [DePaul] [SOC]
Language
en
Communication dans un congrès
This item was published in
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
English Abstract
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 ...Read more >
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.Read less <
ANR Project
Calculabilité et complexité en distribué - ANR-11-BS02-0014
Origin
Hal imported