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

در این مقاله، مسئله ساخت پوشاننده هندسی تحمل پذیر ناحیه-خطا مقید به زیر کلاسی از نواحی محدب، مورد بحث قرار می گیرد. فرض کنید که S مجموعه ای از n نقطه در صفحه باشد. به طور دقیق تر، در این مقاله، یک الگوریتم حریصانه برای ساخت پوشاننده هندسی تحمل-پذیر ناحیه-خطا در حالتی که ناحیه های خطا، مجموعه ای از نیم صفحه ها با مرز موازی با حداکثر k خط است، بررسی می شود. نشان داده می شود که پیچیدگی زمانی الگوریتم پیشنهادی O(kn^۳ log⁡n) و گراف تولید شده توسط آن دارای O(kn) یال است. طبق آخرین اطلاعاتی که داریم بهترین الگوریتمی که برای ساخت یک پوشاننده هندسی تحمل پذیر ناحیه-خطا برای مجموعه نقطه S ارائه شده است، دارای زمان اجرای O(n log^۲⁡n) است و گراف تولید شده توسط آن دارای O(n log⁡n) یال است.

کلیدواژه ها:

پوشاننده هندسی ، شبکه های ارتباطی ، الگوریتم حریصانه