Given a set of points in the plane, we show that the θ-graph with 5 cones is a geometric spanner with spanning ratio at most √50 + 22√5 ≈ 9.960 . This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive argument, giving a, possibly self-intersecting, path between any two vertices, whose length is at most √50 + 22√5 times the Euclidean distance between the vertices. We also give a lower bound on the spanning ratio of 1/2(11√5 - 17) ≈ 3.798.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-642-45043-3_10
Citation
Bose, P, Morin, P, Van Renssen, A. (André), & Verdonschot, S. (Sander). (2013). The θ5-graph is a spanner. doi:10.1007/978-3-642-45043-3_10