The stretch factor of $L_1$- and $L_\infty$-Delaunay triangulations

Darryl Hill

We examine a paper by Bonichon et al., who determine the stretch factor of Delaunay graphs in the $L_1$ and $L_\infty$ metrics to be approximately $2.61$. Their proof is constructive, and they show their bound to be tight by giving a matching lower bound. This improves upon the 25 year old bound of $\sqrt{10}$ by Chew.