Mostrar el registro sencillo del ítem

Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorBONICHON, Nicolas
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierInstitut universitaire de France [IUF]
dc.contributor.authorGAVOILLE, Cyril
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorHANUSSE, Nicolas
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorILCINKAS, David
dc.date.accessioned2024-04-15T09:48:47Z
dc.date.available2024-04-15T09:48:47Z
dc.date.issued2010
dc.date.conference2010-06
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198202
dc.description.abstractEn$\Theta_k$-graphs are geometric graphs that appear in the context of graph navigation. The shortest-path metric of these graphs is known to approximate the Euclidean complete graph up to a factor depending on the cone number $k$ and the dimension of the space. TD-Delaunay graphs, a.k.a.~triangular-distance Delaunay triangulations, introduced by Chew, have been shown to be plane $2$-spanners of the 2D Euclidean complete graph, i.e., the distance in the TD-Delaunay graph between any two points is no more than twice the distance in the plane. Orthogonal surfaces are geometric objects defined from independent sets of points of the Euclidean space. Orthogonal surfaces are well studied in combinatorics (orders, integer programming) and in algebra. From orthogonal surfaces, geometric graphs, called geodesic embeddings can be built. In this paper, we introduce a specific subgraph of the $\TG$-graph defined in the 2D Euclidean space, namely the $\DTG$-graph, composed of the even-cone edges of the $\TG$-graph. Our main contribution is to show that these graphs are exactly the TD-Delaunay graphs, and are strongly connected to the geodesic embeddings of orthogonal surfaces of coplanar points in the 3D Euclidean space. Using these new bridges between these three fields, we establish: \begin{itemize} \item Every $\TG$-graph is the union of two spanning TD-Delaunay graphs. In particular, $\TG$-graphs are $2$-spanners of the Euclidean graph, and the bound of~$2$ on the stretch factor is the best possible. It was not known that $\Theta_6$-graphs are $t$-spanners for some constant $t$, and $\Theta_7$-graphs were only known to be $t$-spanners for $t \approx 7.562$. \item Every plane triangulation is TD-Delaunay realizable, i.e., every combinatorial plane graph for which all its interior faces are triangles is the TD-Delaunay graph of some point set in the plane. Such realizability property does not hold for classical Delaunay triangulations. \end{itemize}
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Berlin / Heidelberg
dc.source.titleProceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science
dc.subject.enDelaunay triangulation
dc.subject.enTheta-graph
dc.subject.enOrthogonal surface
dc.subject.enSpanner
dc.subject.enRealizability
dc.title.enConnections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-16926-7_25
dc.subject.halInformatique [cs]/Géométrie algorithmique [cs.CG]
bordeaux.page266--278
bordeaux.volume6410
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleWG 2010
bordeaux.countryGR
bordeaux.title.proceedingProceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science
bordeaux.peerReviewedoui
hal.identifierhal-00536710
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00536710v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2036th%20International%20Workshop%20on%20Graph%20Theoretic%20Concepts%20in%20Computer%20Science&rft.date=2010&rft.volume=6410&rft.spage=266--278&rft.epage=266--278&rft.au=BONICHON,%20Nicolas&GAVOILLE,%20Cyril&HANUSSE,%20Nicolas&ILCINKAS,%20David&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