Communication-Efficient Construction of the Plane Localized Delaunay Graph

Simple item page
dc.creatorBose, Prosenjit
dc.creatorCarmi, Paz
dc.creatorSmid, Michiel
dc.creatorXu, Daming
dc.date2008-09-17
dc.date.accessioned2026-07-07T10:03:31Z
dc.date.available2026-07-07T10:03:31Z
dc.descriptionLet $V$ be a finite set of points in the plane. We present a 2-local algorithm that constructs a plane $\frac{4 π\sqrt{3}}{9}$-spanner of the unit-disk graph $\UDG(V)$. This algorithm makes only one round of communication and each point of $V$ broadcasts at most 5 messages. This improves the previously best message-bound of 11 by Araújo and Rodrigues (Fast localized Delaunay triangulation, Lecture Notes in Computer Science, volume 3544, 2004).
dc.identifierhttps://arxiv.org/abs/0809.2956
dc.identifierhttp://arxiv.org/abs/0809.2956
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/169316
dc.subjectComputational Geometry
dc.titleCommunication-Efficient Construction of the Plane Localized Delaunay Graph
dc.typetext

Files

Collections

arXiv