Communication-efficient construction of the plane localized Delaunay graph

DOI10.1007/978-3-642-12200-2_26MaRDI QIDQ3557027zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Paz Carmi, Daming Xu, Michiel Smid

Publication date 27 April 2010

Published in LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.2956

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Let $V$ be a finite set of points in the plane. We present a 2-local algorithm that constructs a plane $frac4pisqrt39$-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'{u}jo and Rodrigues (Fast localized Delaunay triangulation, Lecture Notes in Computer Science, volume 3544, 2004).

Recommendations

• Efficient construction of low weight bounded degree planar spanner
• Improved local algorithms for spanner construction
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• On geometric spanners of Euclidean and unit disk graphs
• Principles of Distributed Systems

Cited in

(6)

• Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in \(d\)-dimensions
• The Euclidean bottleneck Steiner path problem and other applications of ( , )-pair decomposition
• Fast and efficient restricted Delaunay triangulation in random geometric graphs
• On plane geometric spanners: a survey and open problems
• Principles of Distributed Systems
• Towards higher-dimensional topological self-stabilization: a distributed algorithm for Delaunay graphs

This page was built for publication: Communication-efficient construction of the plane localized Delaunay graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557027)