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 \(\mathcal{G}\) on a point set P and a region F, we define \(\mathcal{G}\ominus F\) to be what remains of \(\mathcal{G}\) after the vertices and edges of \(\mathcal{G}\) intersecting F have been removed. A \(\mathcal{C}\) -fault tolerant t-spanner is a geometric graph \(\mathcal{G}\) on P such that for any convex region F, the graph \(\mathcal{G}\ominus F\) is a t-spanner for \(\mathcal{G}_{c}(P)\ominus F\) , where \(\mathcal{G}_{c}(P)\) is the complete geometric graph on P. We prove that any set P of n points admits a \(\mathcal{C}\) -fault tolerant (1+ε)-spanner of size \(\mathcal{O}(n\log n)\) for any constant ε>0; if adding Steiner points is allowed, then the size of the spanner reduces to \(\mathcal{O}(n)\) , and for several special cases, we show how to obtain region-fault tolerant spanners of \(\mathcal{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 \(\mathcal{G}\ominus D\) between any two points u,v∈P∖D is at most t times the geodesic distance between u and v in ℝ2∖D. We prove that for any P, we can add \(\mathcal{O}(n)\) Steiner points to obtain a fault-tolerant geodesic (1+ε)-spanner of size \(\mathcal{O}(n)\) .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bollobás, B., Scott, A.: On separating systems. Eur. J. Comb. 28(4), 1068–1071 (2007)
Callahan, P.B., Kosaraju, S.R.: Faster algorithms for some geometric graph problems in higher dimensions. In: SODA’93: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 291–300. Society for Industrial and Applied Mathematics, Philadelphia (1993)
Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42, 67–90 (1995)
Chew, L.P.: There is a planar graph almost as good as the complete graph. In SCG’86: Proceedings of the 2nd Annual ACM Symposium on Computational Geometry, pp. 169–177 (1986)
Clarkson, K.L.: Approximation algorithms for shortest path motion planning. In STOC’87: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 56–65 (1987)
Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. In: SCG’03: Proceedings of the 19th Annual ACM Symposium on Computational Geometry, pp. 1–10. ACM, New York (2003)
Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7, 297–315 (1997)
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)
Duncan, C.A., Goodrich, M.T., Kobourov, S.: Balanced aspect ratio trees: Combining the advances of k-d trees and octrees. J. Algorithms 38, 303–333 (2001)
Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425–461. Elsevier, Amsterdam (2000)
Fischer, J., Har-Peled, S.: Dynamic well-separated pair decomposition made easy. In CCCG’05: Proceedings of the 17th Canadian Conference on Computational Geometry, pp. 235–238 (2005)
Gudmundsson, J., Knauer, C.: Dilation and detour in geometric networks. In: Gonzalez, T. (ed.) Handbook on Approximation Algorithms and Metaheuristics. Chapman & Hall, London (2007)
Hansel, G.: Nombre minimal de contacts de fermeture nécessaires pour réaliser une fonction booléenne symétrique de n variables. C. R. Acad. Sci. Paris 258, 6037–6040 (1964). Russian transl., Kibern. Sb. (Nov. Ser.) 5, 47–52 (1968)
Har-Peled, S.: On the expected complexity of random convex hulls. Technical Report 330/98, School Math. Sci., Tel-Aviv Univ., Tel-Aviv, Israel (1998)
Keil, J.M.: Approximating the complete Euclidean graph. In: SWAT’88: Proceedings of the 1st Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 318, pp. 208–213. Springer, Berlin (1988)
Levcopoulos, C., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32, 144–156 (2002)
Lukovszki, T.: New results of fault tolerant geometric spanners. In: WADS’99: Proceedings of the 6th Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 1663, pp. 193–204. Springer, Berlin (1999)
Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)
Peleg, D., Schäffer, A.: Graph spanners. J. Graph Theory 13, 99–116 (1989)
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)
Rényi, A., Sulanke, R.: Über die konvexe hülle von n zufällig gerwähten punkten I. Z. Wahrscheinlichkeitstheor. Verw. Geb. 2, 75–84 (1963)
Ross, S.: A First Course in Probability, 5th edn. Prentice-Hall, New York (1998)
Salowe, J.S.: Constructing multidimensional spanner graphs. Int. J. Comput. Geom. Appl. 1, 99–107 (1991)
Salowe, J.S.: Enumerating interdistances in space. Int. J. Comput. Geom. Appl. 2(1), 49–59 (1992)
Smid, M.: Closest point problems in computational geometry. In: Sack, J.-R. (ed.) Handbook of Computational Geometry, pp. 877–935. Elsevier, Amsterdam (2000)
Vaidya, P.M.: Minimum spanning trees in k-dimensional space. SIAM J. Comput. 17(3), 572–582 (1988)
Vaidya, P.M.: An O(nlog n) algorithm for the all-nearest-neighbors problem. Discrete Comput. Geom. 4, 101–115 (1989)
Vaidya, P.M.: A sparse graph almost as good as the complete graph on points in K dimensions. Discrete Comput. Geom. 6(4), 369–381 (1991)
Varadarajan, K.R.: A divide-and-conquer algorithm for min-cost perfect matching in the plane. In FOCS’98: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 320–331 (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Joseph S.B. Mitchell.
M.A. Abam was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 612.065.307 and by the MADALGO Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation.
M. de Berg was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.
M. Farshi was supported by Ministry of Science, Research and Technology of I.R. Iran.
NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.
Rights and permissions
About this article
Cite this article
Abam, M.A., de Berg, M., Farshi, M. et al. Region-Fault Tolerant Geometric Spanners. Discrete Comput Geom 41, 556–582 (2009). https://doi.org/10.1007/s00454-009-9137-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9137-7