Mostrar el registro sencillo del ítem

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

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBONICHON, Nicolas
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierInstitut universitaire de France [IUF]
dc.contributor.authorGAVOILLE, Cyril
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorHANUSSE, Nicolas
hal.structure.identifierSchool of Computer Science, Telecommunications, and Information Systems [DePaul] [CTI]
hal.structure.identifierSchool of Computing [DePaul] [SOC]
dc.contributor.authorPERKOVIC, Ljubomir
dc.date.accessioned2024-04-15T09:45:44Z
dc.date.available2024-04-15T09:45:44Z
dc.date.created2012-02-26
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197946
dc.description.abstractEnIn 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.isoen
dc.subject.enDelaunay triangulations
dc.subject.en$L_1$-metric
dc.subject.en$L_\infty$-metric
dc.subject.enstretch factor
dc.title.enThe Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations
dc.typeRapport
dc.subject.halInformatique [cs]/Géométrie algorithmique [cs.CG]
dc.identifier.arxiv1202.5127
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
hal.identifierhal-00673187
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00673187v1
bordeaux.COinSctx_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


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem