Afficher la notice abrégée

The Stretch Factor of ${L}_1$- and ${L}_\infty$-{D}elaunay 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:44:50Z
dc.date.available2024-04-15T09:44:50Z
dc.date.created2012
dc.date.issued2012-09
dc.date.conference2012-09
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197876
dc.description.abstractEnIn this paper we determine the stretch factor of L1-Delaunay and L∞-Delaunay triangulations, and we show that it is equal to √(4 + 2√2) ≈ 2.61. Between any two points x, y of such triangulations, we construct a path whose length is no more than √(4 + 2√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 triangulations of √10 by Chew (SoCG '86). This is the first time the stretch factor of the Lp-Delaunay for any real p ≥ 1, is determined exactly.
dc.description.sponsorshipCalculabilité et complexité en distribué - ANR-11-BS02-0014
dc.language.isoen
dc.source.title20th Annual European Symposium on Algorithms (ESA)
dc.title.enThe Stretch Factor of ${L}_1$- and ${L}_\infty$-{D}elaunay Triangulations
dc.typeCommunication dans un congrès
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page205-216
bordeaux.volume7501 of Lecture Notes in Computer Science
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title20th Annual European Symposium on Algorithms (ESA)
bordeaux.countrySI
bordeaux.title.proceeding20th Annual European Symposium on Algorithms (ESA)
bordeaux.conference.cityLjubljana
bordeaux.peerReviewedoui
hal.identifierhal-00725844
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00725844v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=20th%20Annual%20European%20Symposium%20on%20Algorithms%20(ESA)&rft.date=2012-09&rft.volume=7501%20of%20Lecture%20Notes%20in%20Computer%20Science&rft.spage=205-216&rft.epage=205-216&rft.au=BONICHON,%20Nicolas&GAVOILLE,%20Cyril&HANUSSE,%20Nicolas&PERKOVIC,%20Ljubomir&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée