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*(*n*log *n*) time.