The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations

Details The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations

2012-02-23

arxiv.org/abs/1202.5127v2

Computer Science

Computational Geometry

Scientific paper

In this paper we determine the stretch factor of the $L_1$-Delaunay and $L_\infty$-Delaunay triangulations, and we show that this stretch is $\sqrt{4+2\sqrt{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+2\sqrt{2}}$ times the Euclidean distance between $x$ and $y$, and this bound is best possible. This definitively improves the 25-year old bound of $\sqrt{10}$ by Chew (SoCG '86). To the best of our knowledge, this is the first time the stretch factor of the well-studied $L_p$-Delaunay triangulations, for any real $p\ge 1$, is determined exactly.

Affiliated with

Also associated with

No associations

Rating

The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-659490