  The greedy spanner is the highest quality geometric spanner (in e.g. edge
count and weight, both in theory and practice) known to be computable in
polynomial time. Unfortunately, all known algorithms for computing it take
Omega(n^2) time, limiting its applicability on large data sets.
  We observe that for many point sets, the greedy spanner has many `short'
edges that can be determined locally and usually quickly, and few or no `long'
edges that can usually be determined quickly using local information and the
well-separated pair decomposition. We give experimental results showing large
to massive performance increases over the state-of-the-art on nearly all tests
and real-life data sets. On the theoretical side we prove a near-linear
expected time bound on uniform point sets and a near-quadratic worst-case
bound.
  Our bound for point sets drawn uniformly and independently at random in a
square follows from a local characterization of t-spanners we give on such
point sets: we give a geometric property that holds with high probability on
such point sets. This property implies that if an edge set on these points has
t-paths between pairs of points `close' to each other, then it has t-paths
between all pairs of points.
  This characterization gives a O(n log^2 n log^2 log n) expected time bound on
our greedy spanner algorithm, making it the first subquadratic time algorithm
for this problem on any interesting class of points. We also use this
characterization to give a O((n + |E|) log^2 n log log n) expected time
algorithm on uniformly distributed points that determines if E is a t-spanner,
making it the first subquadratic time algorithm for this problem that does not
make assumptions on E.
