Partitioned Neighborhood Spanners of Minimal Outdegree
Matthias Fischer, Tamas Lukovszki, Martin Ziegler
Abstract
A geometric spanner with vertex set P in 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 and the stretch
factor f>1 describing the
"quality" of approximation.
PNGs have been throughly investigated with respect to small values of f.
We, on the other hand,
present in this work results about small values of k.
The aim of minimizing this parameter rather than
the first one arises from two observations:
- It 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 constructive and yield efficient
algorithms for actually
computing the corresponding graphs even in degenerate cases.