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