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~(1/2))~(1/2) ≈ 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~(1/2))~(1/2) times the Euclidean distance between the vertices. We also give a lower bound on the spanning ratio of 1/2(11 5~(1/2) - 17) ≈ 3.798.
展开▼
