Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We introduce the concept of region-fault tolerant spanners for planar point sets, and prove the existence of region-fault tolerant spanners of small size. For a geometric graph G on a point set P and a region F, we define G ⊖ F to be what remains of G after the vertices and edges of G intersecting F have been removed. A C-fault tolerant t-spanner is a geometric graph G on P such that for any convex region F, the graph G ⊖ F is a t-spanner for Gc(P)⊖F, where Gc(P) is the complete geometric graph on P. We prove that any set P of n points admits a C-fault tolerant (1 + ε)-spanner of size O(n log n), for any constant ε > 0; if adding Steiner points is allowed then the size of the spanner reduces to O(n), and for several special cases we show how to obtain region-fault tolerant spanners of O(n) size without using Steiner points. We also consider fault-tolerant geodesic t-spanners: this is a variant where, for any disk D, the distance in G ⊖ D between any two points u, v ε P \ D is at most t times the geodesic distance between u and v in R² \ D. We prove that for any P we can add O(n) Steiner points to obtain a fault-tolerant geodesic (1 + ε)-spanner of size O(n).

REFERENCES

• 1: Paul B. Callahan , S. Rao Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.291-300, January 25-27, 1993, Austin, Texas, United States
• 2: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 3: P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
• 4: K. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.56-65, January 1987, New York, New York, United States [doi>10.1145/28395.28402]
• 5: Artur Czumaj , Hairong Zhao, Fault-tolerant geometric spanners, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777794]
• 6: G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean spanners. International Journal of Computational Geometry and Applications, 7:297--315, 1997.
• 7: Christian A. Duncan , Michael T. Goodrich , Stephen Kobourov, Balanced aspect ratio trees: combining the advantages of k-d trees and octrees, Journal of Algorithms, v.38 n.1, p.303-333, Jan. 2001 [doi>10.1006/jagm.2000.1135]
• 8: D. Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 425--461. Elsevier Science Publishers, Amsterdam, 2000.
• 9: J. Fischer and S. Har-Peled. Dynamic well-separated pair decomposition made easy. In Proc. of the 17th Canadian Conference on Computational Geometry (CCCG'05), pages 235--238, 2005.
• 10: J. Gudmundsson and C. Knauer. Dilation and detour in geometric networks. In T. Gonzalez, editor, To appear in Handbook on approximation algorithms and metaheuristics. Chapman & Hall/CRC, Amsterdam, 2006.
• 11: J. M. Keil, Approximating the complete Euclidean graph, No. 318 on SWAT 88: 1st Scandinavian workshop on algorithm theory, p.208-213, January 1988, Halmstad, Sweden
• 12: C. Levcopoulos, G. Narasimhan, and M. Smid. Improved algorithms for constructing fault-tolerant spanners. Algorithmica, 32:144--156, 2002.
• 13: Tamás Lukovszki, New Results of Fault Tolerant Geometric Spanners, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.193-204, August 11-14, 1999
• 14: Giri Narasimhan , Michiel Smid, Geometric Spanner Networks, Cambridge University Press, New York, NY, 2007
• 15: D. Peleg and A. Schäffer. Graph spanners. Journal of Graph Theory, 13:99--116, 1989.
• 16: A. Rényi and R. Sulanke. Über die konvexe hülle von n zufällig gerwähten punkten. I. Z. Wahrsch. Verw. Gebiete, 2:75--84, 1963.
• 17: J. S. Salowe. Constructing multidimensional spanner graphs. International Journal of Computational Geometry & Applications, 1:99--107, 1991.
• 18: J. S. Salowe. Enumerating interdistances in space. Int. J. Comput. Geometry Appl., 2(1):49--59, 1992.
• 19: M. Smid. Closest point problems in computational geometry. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 877--935. Elsevier Science Publishers, Amsterdam, 2000.
• 20: Pravin M. Vaidya, Minimum spanning trees in k-dimensional space, SIAM Journal on Computing, v.17 n.3, p.572-582, June 1988 [doi>10.1137/0217035]
• 21: P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry, v.4 n.2, p.101-115, Jan. 1989 [doi>10.1007/BF02187718]
• 22: Pravin M. Vaidya, A sparse graph almost as good as the complete graph on points in K dimensions, Discrete & Computational Geometry, v.6 n.4, p.369-381, 1991 [doi>10.1007/BF02574695]
• 23: Kasturi R. Varadarajan, A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.320, November 08-11, 1998