فهرست نشریات علمی دسترسی آزاد ایران

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