---
res:
bibo_abstract:
- "A geometric spanner with vertex set P in Rd 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 in N and the stretch factor f>1 describing the \x93quality\x94
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:\r\n\r\n* k determines
the amount of space required for storing PNGs.\r\n\r\n* Many algorithms employing
a (previously constructed) spanner have running times depending on its outdegree.\r\n\r\nOur
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.\r\n@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Matthias
foaf_name: Fischer, Matthias
foaf_surname: Fischer
foaf_workInfoHomepage: http://www.librecat.org/personId=146
- foaf_Person:
foaf_givenName: Tamas
foaf_name: Lukovszki, Tamas
foaf_surname: Lukovszki
- foaf_Person:
foaf_givenName: Martin
foaf_name: Ziegler, Martin
foaf_surname: Ziegler
dct_date: 1999^xs_gYear
dct_language: eng
dct_title: Partitioned neighborhood spanners of minimal outdegree@
...