Evènement pour le 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