یک الگوریتم حریصانه برای ساخت پوشاننده هندسی تحمل‌پذیر ناحیه-خطا

در این مقاله، مسئله ساخت پوشاننده هندسی تحمل‌پذیر ناحیه خطا مقید به زیر کلاسی از نواحی محدب، مورد بحث قرار می‌گیرد. فرض کنید که s مجموعه‌ای از n نقطه در صفحه باشد.ﻪ ﻃﻮر دﻗﯿﻖ ﺗﺮ، در اﯾﻦ ﻣﻘﺎﻟﻪ، ﯾﮏ اﻟﮕﻮرﯾﺘﻢ ﺣﺮﯾﺼﺎﻧﻪ ﺑﺮای ﺳﺎﺧﺖ ﭘﻮﺷﺎﻧﻨﺪه ﻫﻨﺪﺳﯽ ﺗﺤﻤﻞ ﭘﺬﯾﺮ ﻧﺎﺣﯿﻪ-ﺧﻄﺎ در ﺣﺎﻟﺘﯽ ﮐﻪ ﻧﺎﺣﯿﻪ ﻫﺎی ﺧﻄﺎ، ﻣﺠﻤﻮﻋﻪ ای از ﻧﯿﻢ ﺻﻔﺤﻪ ﻫﺎ ﺑﺎ ﻣﺮز ﻣﻮازی ﺑﺎ ﺣﺪاﮐﺜﺮ ﺧﻂ اﺳﺖ، ﺑﺮرﺳﯽ ﻣﯽ ﺷﻮد. ﻧﺸﺎن داده ﺷﺪه اﺳﺖ ﮐﻪ ﭘﯿﭽﯿﺪﮔﯽ زﻣﺎﻧﯽ اﻟﮕﻮرﯾﺘﻢ ﭘﯿشنهادی o kn^3 logn⁡ و گراف تولید شده توسط آن دارای o kn یال است. طبق آخرین اطلاعاتی که داریم بهترین الگوریتمی که برای ساخت یک پوشاننده هندسی تحمل پذیر ناحیه خطا برای مجموعه نقطیه - ارائیه شیده اسیت، دارای زمان اجرایo n log^3n⁡است و گراف تولید شده توسط آن دارای o n logn⁡ یال است.

a greedy algorithm for constructing region-fault tolerant geometric spanners

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.