Local Routing in Convex Subdivisions

Prosenjit Bose, Stephane Durocher, Debajyoti Mondal, Maxime Peabody, Matthew Skala, Mohammad Abdul Wahid

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review


In various wireless networking settings, node locations determine a network’s topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required Θ(logn) state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and the first local geometric memoryless routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions) when the algorithm has knowledge of the incoming port (the preceding node on the route).
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)140
Number of pages151
Publication statusPublished - 2015
Externally publishedYes


Dive into the research topics of 'Local Routing in Convex Subdivisions'. Together they form a unique fingerprint.

Cite this