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