Let S be a set of n points in ℝd. A graph G = (S,E) is called a t-spanner for S, if for any two points p and q in S, the shortest-path distance in G between p and q is at most t|pq|, where |pq| denotes the Euclidean distance between p and q. The graph G is called θ-angle-constrained, if any two distinct edges sharing an endpoint make an angle of at least θ. It is shown that, for any θ with 0 < θ < π/3, a θ-angle-constrained t-spanner can be computed in O(n logn) time, where t depends only on θ.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-642-17517-6_29
Citation
Carmi, P. (Paz), & Smid, M. (2010). An optimal algorithm for computing angle-constrained spanners. doi:10.1007/978-3-642-17517-6_29