Partitioned Neighborhood Spanners of Minimal Outdegree
Abstract:
A geometric spanner with vertex set P⊂R^{d} is a
sparse approximation of the complete Euclidean graph
determined by P. We introduce the notion of partitioned
neighborhood graphs (PNGs), unifying and generalizing
most constructions of spanners treated in literature.
Two important parameters characterizing their properties
are the outdegree k∈N and the
stretch factor f>1 describing the `quality' of
approximation.
PNGs have been throughly investigated
with respect to small values of f. We
present in this work results about small values of k.
The aim of minimizing k
rather than f arises from two observations:
- k determines the amount of space required for storing PNGs.
- Many algorithms employing a (previously constructed)
spanner have running times depending on its outdegree.
Our results include, for fixed dimensions d as well as
asymptotically, upper and lower bounds on this optimal
value of k. The upper bounds are shown constructively and
yield efficient algorithms for actually computing
the corresponding PNGs even in degenerate cases.
Full Paper