Angle-Monotone Graphs: Construction and Local Routing
share
A geometric graph in the plane is angle-monotone of width γ if every pair of vertices is connected by an angle-monotone path of width γ, a path such that the angles of any two edges in the path differ by at most γ. Angle-monotone graphs have good spanning properties. We prove that every point set in the plane admits an angle-monotone graph of width 90^∘, hence with spanning ratio √(2), and a subquadratic number of edges. This answers an open question posed by Dehkordi, Frati and Gudmundsson. We show how to construct, for any point set of size n and any angle α, 0 < α < 45^∘, an angle-monotone graph of width (90^∘+α) with O(n/α) edges. Furthermore, we give a local routing algorithm to find angle-monotone paths of width (90^∘+α) in these graphs. The routing ratio, which is the ratio of path length to Euclidean distance, is at most 1/cos(45^∘ + α/2), i.e., ranging from √(2)≈ 1.414 to 2.613. For the special case α = 30^∘, we obtain the Θ_6-graph and our routing algorithm achieves the known routing ratio 2 while finding angle-monotone paths of width 120^∘.
READ FULL TEXT