The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | BONICHON, Nicolas | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Institut universitaire de France [IUF] | |
| dc.contributor.author | GAVOILLE, Cyril | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | HANUSSE, Nicolas | |
| hal.structure.identifier | School of Computer Science, Telecommunications, and Information Systems [DePaul] [CTI] | |
| hal.structure.identifier | School of Computing [DePaul] [SOC] | |
| dc.contributor.author | PERKOVIC, Ljubomir | |
| dc.date.accessioned | 2024-04-15T09:45:44Z | |
| dc.date.available | 2024-04-15T09:45:44Z | |
| dc.date.created | 2012-02-26 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197946 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.subject.en | Delaunay triangulations | |
| dc.subject.en | $L_1$-metric | |
| dc.subject.en | $L_\infty$-metric | |
| dc.subject.en | stretch factor | |
| dc.title.en | The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations | |
| dc.type | Rapport | |
| dc.subject.hal | Informatique [cs]/Géométrie algorithmique [cs.CG] | |
| dc.identifier.arxiv | 1202.5127 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| hal.identifier | hal-00673187 | |
| hal.version | 1 | |
| hal.audience | Non spécifiée | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00673187v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=BONICHON,%20Nicolas&GAVOILLE,%20Cyril&HANUSSE,%20Nicolas&PERKOVIC,%20Ljubomir&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||