2018/01/19 by Lubiw, Anna, Mondal, Debajyoti
#65D18 #68Q25 #Computational Geometry (cs.CG) #FOS: Computer and information sciences #I.3.5
paper · doi:10.48550/arxiv.1801.06290
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(\fracnα) 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^∘ + \fracα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^∘.