چکیده:
در این مقاله، مسئله ساخت پوشاننده هندسی تحملپذیر ناحیه-خطا مقید به زیر کلاسی از نواحی محدب، مورد بحث قرار میگیرد. فرض کنید که S مجموعهای از n نقطه در صفحه باشد. به طور دقیقتر، در این مقاله، یک الگوریتم حریصانه برای ساخت پوشاننده هندسی تحمل-پذیر ناحیه-خطا در حالتی که ناحیههای خطا، مجموعه ای از نیم صفحه ها با مرز موازی با حداکثر k خط است، بررسی میشود. نشان داده میشود که پیچیدگی زمانی الگوریتم پیشنهادی O(kn^3 logn) و گراف تولید شده توسط آن دارای O(kn) یال است. طبق آخرین اطلاعاتی که داریم بهترین الگوریتمی که برای ساخت یک پوشاننده هندسی تحملپذیر ناحیه-خطا برای مجموعه نقطه S ارائه شده است، دارای زمان اجرای O(n log^2n) است و گراف تولید شده توسط آن دارای O(n logn) یال است.
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 logn ), 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^2n) time and the generated graph has O(n logn) edges.