20101201
An optimal algorithm for computing angleconstrained spanners
Publication
Publication
Let S be a set of n points in ℝd. A graph G = (S,E) is called a tspanner for S, if for any two points p and q in S, the shortestpath distance in G between p and q is at most tpq, where pq denotes the Euclidean distance between p and q. The graph G is called θangleconstrained, if any two distinct edges sharing an endpoint make an angle of at least θ. It is shown that, for any θ with 0 < θ < π/3, a θangleconstrained tspanner can be computed in O(n logn) time, where t depends only on θ.
Additional Metadata  

Persistent URL  dx.doi.org/10.1007/9783642175176_29 
Citation 
Carmi, P. (Paz), & Smid, M. (2010). An optimal algorithm for computing angleconstrained spanners. doi:10.1007/9783642175176_29
