Partitioned neighborhood spanners of minimal outdegree

M. Fischer, T. Lukovszki, M. Ziegler, in: Proceedings of the 11th Canadian Conference on Computational Geometry, Vancouver, 1999.

Download
Restricted hni-id-729.pdf 209.42 KB
Conference Paper | English
Author
Fischer, MatthiasLibreCat; Lukovszki, Tamas; Ziegler, Martin
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 “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.
Publishing Year
Proceedings Title
Proceedings of the 11th Canadian Conference on Computational Geometry
LibreCat-ID

Cite this

Fischer M, Lukovszki T, Ziegler M. Partitioned neighborhood spanners of minimal outdegree. In: Proceedings of the 11th Canadian Conference on Computational Geometry. Vancouver; 1999.
Fischer, M., Lukovszki, T., & Ziegler, M. (1999). Partitioned neighborhood spanners of minimal outdegree. In Proceedings of the 11th Canadian Conference on Computational Geometry. Vancouver.
@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} }
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.
M. Fischer, T. Lukovszki, and M. Ziegler, “Partitioned neighborhood spanners of minimal outdegree,” in Proceedings of the 11th Canadian Conference on Computational Geometry, 1999.
Fischer, Matthias, et al. “Partitioned Neighborhood Spanners of Minimal Outdegree.” Proceedings of the 11th Canadian Conference on Computational Geometry, 1999.
Main File(s)
File Name
hni-id-729.pdf 209.42 KB
Access Level
Restricted Closed Access
Last Uploaded
2020-08-27T11:14:43Z


External material:
Confirmation Letter

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar