Optimal bounds on theta-graphs: More is not always better
We present tight upper and lower bounds on the span- ning ratio of a large family of θ-graphs. We show that θ- graphs with 4k+2 cones (k ≥ 1 and integer) have a span- ning ratio of 1 + 2 sin(θ/2), where θ is 2=(4k + 2). We also show that θ-graphs with 4k + 4 cones have span- ning ratio at least 1+2 tan(θ/2)+2 tan2(θ/2), where θ is 2π=(4k + 4). This is somewhat surprising since, for equal values of k, the spanning ratio of θ -graphs with 4k+4 cones is greater than that of θ-graphs with 4k+2 cones, showing that increasing the number of cones can make the spanning ratio worse.
|Conference||24th Canadian Conference on Computational Geometry, CCCG 2012|
Bose, P, De Carufel, J.-L. (Jean-Lou), Morin, P, Van Renssen, A. (André), & Verdonschot, S. (Sander). (2012). Optimal bounds on theta-graphs: More is not always better. Presented at the 24th Canadian Conference on Computational Geometry, CCCG 2012.