Anthony D'Angelo

Recently, deterministic geometric local routing algorithms were presented with guaranteed delivery for convex subdivisions using only one bit and for monotone subdivisions using only predecessor awareness (in "Local Routing in Convex Subdivisions", SOFSEM 2015: 140-151). We present a simple deterministic geometric local routing algorithm that guarantees delivery in monotone planar subdivisions (which include convex subdivisions) without a general position assumption. Our algorithm uses $\lceil \log_2{(d + 1)}\rceil$ bits of extra memory per message, where the $d$ possible edge directions are fixed to $d/2$ different slopes.