An optimal algorithm for computing angle-constrained spanners

Michiel Smid

Let S be a set of n points in R^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 θ.

I will show that such spanners can be computed in O(nlog n) time.