Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
The Stretch Factor of L 1- and L ∞ -Delaunay Triangulations
verfasst von : Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perković
Erschienen in: Algorithms – ESA 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we determine the stretch factor of
L
1
-Delaunay and
L
∞
-Delaunay triangulations, and we show that it is equal to
$\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 the best possible. This definitively improves the 25-year old bound of
$\sqrt{10}$
by Chew (SoCG ’86). This is the first time the stretch factor of the
L
p
-Delaunay triangulations, for any real
p
≥ 1, is determined exactly.