---
_id: '17864'
abstract:
- lang: eng
text: "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"
author:
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Tamas
full_name: Lukovszki, Tamas
last_name: Lukovszki
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: 'Fischer M, Lukovszki T, Ziegler M. Partitioned neighborhood spanners of minimal
outdegree. In: *Proceedings of the 11th Canadian Conference on Computational
Geometry*. Vancouver; 1999.'
apa: Fischer, M., Lukovszki, T., & Ziegler, M. (1999). Partitioned neighborhood
spanners of minimal outdegree. In *Proceedings of the 11th Canadian Conference
on Computational Geometry*. Vancouver.
bibtex: '@inproceedings{Fischer_Lukovszki_Ziegler_1999, place={Vancouver}, title={Partitioned
neighborhood spanners of minimal outdegree}, booktitle={Proceedings of the 11th
Canadian Conference on Computational Geometry}, author={Fischer, Matthias and
Lukovszki, Tamas and Ziegler, Martin}, year={1999} }'
chicago: Fischer, Matthias, Tamas Lukovszki, and Martin Ziegler. “Partitioned Neighborhood
Spanners of Minimal Outdegree.” In *Proceedings of the 11th Canadian Conference
on Computational Geometry*. Vancouver, 1999.
ieee: M. Fischer, T. Lukovszki, and M. Ziegler, “Partitioned neighborhood spanners
of minimal outdegree,” in *Proceedings of the 11th Canadian Conference on Computational
Geometry*, 1999.
mla: Fischer, Matthias, et al. “Partitioned Neighborhood Spanners of Minimal Outdegree.”
*Proceedings of the 11th Canadian Conference on Computational Geometry*,
1999.
short: 'M. Fischer, T. Lukovszki, M. Ziegler, in: Proceedings of the 11th Canadian
Conference on Computational Geometry, Vancouver, 1999.'
date_created: 2020-08-12T13:12:00Z
date_updated: 2022-01-06T06:53:21Z
ddc:
- '000'
department:
- _id: '63'
file:
- access_level: closed
content_type: application/pdf
creator: koala
date_created: 2020-08-27T11:14:43Z
date_updated: 2020-08-27T11:14:43Z
file_id: '18438'
file_name: hni-id-729.pdf
file_size: 209419
relation: main_file
success: 1
file_date_updated: 2020-08-27T11:14:43Z
has_accepted_license: '1'
language:
- iso: eng
place: Vancouver
publication: Proceedings of the 11th Canadian Conference on Computational Geometry
related_material:
link:
- relation: confirmation
url: http://www.cccg.ca/proceedings/1999/fp36.pdf
status: public
title: Partitioned neighborhood spanners of minimal outdegree
type: conference
user_id: '15415'
year: '1999'
...