یک الگوریتم حریصانه برای ساخت پوشاننده هندسی تحملپذیر ناحیه-خطا | ||
| پدافند الکترونیکی و سایبری | ||
| مقاله 8، دوره 10، شماره 4 - شماره پیاپی 40، زمستان 1401، صفحه 75-80 اصل مقاله (836.64 K) | ||
| نوع مقاله: مقاله پژوهشی | ||
| نویسندگان | ||
| داود بخشش* 1؛ محمد فرشی2 | ||
| 1استادیار، گروه علوم کامپیوتر، دانشگاه بجنورد، بجنورد، ایران | ||
| 2دانشیار، دانشکده علوم ریاضی، دانشگاه یزد، یزد، ایران | ||
| چکیده | ||
| در این مقاله، مسئله ساخت پوشاننده هندسی تحملپذیر ناحیه-خطا مقید به زیر کلاسی از نواحی محدب، مورد بحث قرار میگیرد. فرض کنید که S مجموعهای از n نقطه در صفحه باشد. به طور دقیقتر، در این مقاله، یک الگوریتم حریصانه برای ساخت پوشاننده هندسی تحمل-پذیر ناحیه-خطا در حالتی که ناحیههای خطا، مجموعه ای از نیم صفحه ها با مرز موازی با حداکثر k خط است، بررسی میشود. نشان داده میشود که پیچیدگی زمانی الگوریتم پیشنهادی O(kn^3 logn) و گراف تولید شده توسط آن دارای O(kn) یال است. طبق آخرین اطلاعاتی که داریم بهترین الگوریتمی که برای ساخت یک پوشاننده هندسی تحملپذیر ناحیه-خطا برای مجموعه نقطه S ارائه شده است، دارای زمان اجرای O(n log^2n) است و گراف تولید شده توسط آن دارای O(n logn) یال است. | ||
| کلیدواژهها | ||
| پوشاننده هندسی؛ شبکههای ارتباطی؛ الگوریتم حریصانه | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 327 تعداد دریافت فایل اصل مقاله: 344 |
||