A Greedy Algorithm for Constructing Region-Fault Tolerant Geometric Spanners

Document Type : Original Article

Authors

1 Assistant Professor, Department of Computer Science, Bojnord University, Bojnord, Iran

2 Associate Professor, Faculty of Mathematical Sciences, Yazd University, Yazd, Iran

Abstract

In this paper, we consider the problem of constructing the region-fault tolerant geometric spanners when the problem is restricted to a subclass of convex regions. Let S be a set of n points in the plane. In particular, in this paper, a greedy algorithm for constructing the region-fault tolerant geometric spanner of S where the region faults are a set of at most k half-planes with parallel boundaries is presented. We show that the proposed algorithm has the time complexity O(kn^3 log⁡n ), and the generated graph contains O(kn) edges. To the best of our knowledge, the best-known algorithm to construct the region-fault tolerant geometric spanner of S takes O(n log^2⁡n) time and the generated graph has O(n log⁡n) edges.

Keywords

Smiley face

References

[1] A. B. Dehkordi, M. R. Soltanaghaie, F. Z. Boroujeni, “Distributed Denial of Service Attacks Detection in Software Defined Networks,” Jourrnal of  Electronical & Cyber Defence, vol. 9, no. 1, pp. 43-59, 2021. (In Persian)
[2] K. Shoshian, A. Mirghadri, “Modeling of Obfuscated Multi- Stage cyber Attacks,” Jourrnal of Electronical & Cyber Defence, vol. 8, no. 2, pp. 61-73, 2020. (In Persian)
[3] M. A. Abam, M. de Berg, M. Farshi, and J. Gudmundsson, “Region-fault tolerant geometric spanners,” Discrete. Comput. Geom., vol. 41, no. 4, pp. 556-582, 2009.
[4] S. Arya, D. M. Mount, and M. Smid, “Randomized and deterministic algorithms for geometric spanners of small diameter,” 35th Annual Symposium on Foundations of Computer Science, 1994.
[5] P. B. Callahan and S. R. Kosaraju, “Faster algorithms for some geometric graph problems in higher dimensions,” fourth annual ACM-SIAM Symposium on Discrete Algorithms, 1993.
[6] P. B. Callahan and S. R. Kosaraju, “A decomposition of multidimensional point sets with applications to nearest-neighbors and body potential fields,” J. ACM., vol. 42, no. 1, pp. 67-90, 1995.
[7] D. Bakhshesh, L. Barba, P. Bose, J.-L. De Carufel, M. Damian, R. Fagerberg, M. Farshi, A. van Renssen, P. Taslakian, and S. Verdonschot, “Continuous Yao graphs,” Comp. Geom-Theor. Appl., vol. 67, pp. 42-52, 2018.
[8] D. Bakhshesh and M. Farshi, “Fault tolerancy of continuous Yao graph of angle less than ,” Inform. Process. Lett., vol. 148, pp. 13-18, 2019.
[9] P. Bose, P. Carmi, M. Farshi, A. Maheshwari, and M. H. M. Smid, “Computing the greedy spanner in near-quadratic time,” Algorithmica, vol. 58, no. 3, pp. 711-729, 2010.
[10] G. Narasimhan and M. Smid, “Geometric spanner networks”, Cambridge University, 2007.

Files

History

  • Receive Date: 16 February 2022
  • Revise Date: 17 August 2022
  • Accept Date: 05 September 2022
  • Publish Date: 21 January 2023

Share

How to cite

Statistics