DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
Abstract
Given a triangulation G, whose vertex set V is a set of n points in the plane, and given a real number γ with 0 < γ < π, we design an O(n)-time algorithm that constructs a connected subgraph G' of G with vertex set V whose maximum degree is at most 14 + ⌈2π/γ⌉. If G is the Delaunay triangulation of V, and γ = 2π/3, we show that G' is a t-spanner of V (for some constant t) with maximum degree at most 17, thereby improving the previously best known degree bound of 23. If G is a triangulation satisfying the diamond property, then for a specific range of values of γ dependent on the angle of the diamonds, we show that G' is a t-spanner of V (for some constant t) whose maximum degree is bounded by a constant dependent on γ. If G is the graph consisting of all Delaunay edges of length at most 1, and γ = π/3, we show that a modified version of the algorithm produces a plane subgraph G' of the unit-disk graph which is a t-spanner (for some constant t) of the unit-disk graph of V, whose maximum degree is at most 20, thereby improving the previously best known degree bound of 25.
This research was supported by the Natural Sciences and Engineering Research Council of Canada.
References
- Algorithmica 42, 249 (2005), DOI: 10.1007/s00453-005-1168-8. Crossref, Web of Science, Google Scholar
P. Bose , A. Lee and M. Smid , On generalized diamond spanners, Proc. 10th Workshop on Algorithms and Data Structures (WADS)4619,Lecture Notes in Computer Science (Springer-Verlag, Berlin, 2007) pp. 325–336. Google Scholar- Comput. Geom.: Th. Appl. 29, 233 (2004), DOI: 10.1016/j.comgeo.2004.04.003. Crossref, Web of Science, Google Scholar
- SIAM J. Comput. 33, 937 (2004), DOI: 10.1137/S0097539700369387. Crossref, Web of Science, Google Scholar
- J. Comput. Syst. Sci. 39, 205 (1989). Crossref, Web of Science, Google Scholar
G. Das and D. Joseph , Which triangulations approximate the complete graph?, Proc. Int. Symp. Optimal Algorithms401,Lecture Notes in Computer Science (Springer-Verlag, Berlin, 1989) pp. 168–192. Google Scholar- Discr. Comput. Geom. 5, 399 (1990), DOI: 10.1007/BF02187801. Crossref, Web of Science, Google Scholar
- Discr. Comput. Geom. 7, 13 (1992), DOI: 10.1007/BF02187821. Crossref, Web of Science, Google Scholar
- Int. J. Comput. Geom. Appl. 14, 69 (2004), DOI: 10.1142/S0218195904001366. Link, Web of Science, Google Scholar
-
G. Narasimhan and M. Smid , Geometric Spanner Networks ( Cambridge University Press , Cambridge, UK , 2007 ) . Crossref, Google Scholar
Remember to check out the Most Cited Articles! |
---|
Check out these titles in image analysis! |