Abstract
We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs (p,r) where p is a point in the plane and r is a real number. The distance between two points (p i ,r i ) and (p j ,r j ) is defined as |p i p j | − r i − r j . We show that in the case where all r i are positive numbers and |p i p j | ≥ r i + r j for all i,j (in which case the points can be seen as non-intersecting disks in the plane), a variant of the Yao graph is a (1 + ε)-spanner that has a linear number of edges. We also show that the Additively Weighted Delaunay graph (the face-dual of the Additively Weighted Voronoi diagram) has constant spanning ratio. The straight line embedding of the Additively Weighted Delaunay graph may not be a plane graph. Given the Additively Weighted Delaunay graph, we show how to compute a plane embedding with a constant spanning ratio in O(nlogn) time.
Research partially supported by NSERC, MRI, CFI, and MITACS.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bose, P., Carmi, P., Couture, M.: Spanners of additively weighted point sets. CoRR abs/0801.4013 (2008)
Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, New York (2007)
Yao, A.C.C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11(4), 721–736 (1982)
Ruppert, J., Seidel, R.: Approximating the d-dimensional complete euclidean graph. In: CCCG 1991: Proceedings of the 3rd Canadian Conference on Computational Geometry, pp. 207–210 (1991)
Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete Euclidean graph. Discrete Comput. Geom. 7(1), 13–28 (1992)
Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM 42, 67–90 (1995)
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Heidelberg (1997)
Fortune, S.: A sweepline algorithm for voronoi diagrams. Algorithmica 2, 153–174 (1987)
Lee, D.T., Drysdale, R.L.: Generalization of voronoi diagrams in the plane. SIAM Journal on Computing 10(1), 73–87 (1981)
Okabe, A., Boots, B., Sugihara, K.: Spatial tessellations: concepts and applications of Voronoi diagrams, 2nd edn. John Wiley & Sons, Inc. New York (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bose, P., Carmi, P., Couture, M. (2008). Spanners of Additively Weighted Point Sets. In: Gudmundsson, J. (eds) Algorithm Theory – SWAT 2008. SWAT 2008. Lecture Notes in Computer Science, vol 5124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69903-3_33
Download citation
DOI: https://doi.org/10.1007/978-3-540-69903-3_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69900-2
Online ISBN: 978-3-540-69903-3
eBook Packages: Computer ScienceComputer Science (R0)