Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
The Stretch Factor of $L_1$- and $L_infty$-Delaunay Triangulations
du groupe GT Graphes et Applications

Date 2012-09-21  14:00-15:00
TitreThe Stretch Factor of $L_1$- and $L_infty$-Delaunay Triangulations  
RésuméIn this talk I will show that the stretch factor of $L_1$-Delaunay and $L_infty$-Delaunay triangulations is equal to $sqrt{4+2sqrt{2}} approx 2.61$. Between any two points $x,y$ of such triangulations, we construct a path whose length is no more than $sqrt{4+2sqrt{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 $sqrt{10}$ by Chew (SoCG '86). This work presented at ESA'12 is in collaboration with N. Bonichon, N. Hanusse and L. Perkovic.  
LieuSalle 178 
OrateurCyril Gavoille 



Aucun document lié à cet événement.

Retour
Retour à l'index