Angle-Monotone Graphs: Construction and Local Routing

Abstract

A geometric graph in the plane is angle-monotone of width $\gamma$ if every pair of vertices is connected by an angle-monotone path of width $\gamma$, a path such that the angles of any two edges in the path differ by at most $\gamma$. Angle-monotone graphs have good spanning properties. We prove that every point set in the plane admits an angle-monotone graph of width $90^{\circ }$, hence with spanning ratio $\sqrt{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 $\alpha$, $0<\alpha <45^{\circ }$, an angle-monotone graph of width $(90^{\circ }+\alpha )$ with $O(\frac{n}{\alpha })$ edges. Furthermore, we give a local routing algorithm to find angle-monotone paths of width $(90^{\circ }+\alpha )$ in these graphs. The routing ratio, which is the ratio of path length to Euclidean distance, is at most $1/\cos (45^{\circ }+\frac{\alpha }{2})$, i.e., ranging from $\sqrt{2}\approx 1.414$ to $2.613$. For the special case $\alpha =30^{\circ }$, we obtain the ${\Theta }_6$-graph and our routing algorithm achieves the known routing ratio 2 while finding angle-monotone paths of width $120^{\circ }$.

References in corpus (1)

• Angle-monotone Paths in Non-obtuse Triangulations