نمودار قطبی نقاط با قطب متحرک
الموضوعات : جنرال لواءبهرام صادقی بی غم 1 , فاطمه ربانی 2
1 - دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه زنجان
2 - دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه زنجان
الکلمات المفتاحية: نمودار قطبی, نمودار ورونوی, مخابرات, آنتن, زاویه قطبی, رویت پذیری,
ملخص المقالة :
مسئله نمودار قطبی یکی از تعمیم‌های نمودار ورونوی است که در آن به جای متر اقلیدسی از مقدار زاویه برای محاسبه فاصله استفاده می شود.. این مسئله کاربردهای زیادی در پردازش تصویر، مخابرات و مباحث مربوط به آنتن، رؤیت‌پذیری و مسیریابی ربات دارد. در سالهای اخیر دو نوع نمودار قطبی مطرح شده و برای انواع سایت‌ها الگوریتم‌های مناسبی ارائه شده است. همچنین روی همین مسائل با داده‌های جنبشی و حالات پویا الگوریتم‌هایی ارائه شده است. در این مقاله قطب به عنوان ناظرمتحرک در نظر گرفته شده و الگوریتمی ارائه می‌شود که مسئله بازسازی نمودار قطبی با قطب نزدیک را به صورت کارا و در زمان خطی حل می‌کند. در این حالت زمان پیش‌پردازش الگوریتم〖O(n^4 log〗_2〖n)〗 و زمان باز رسم نمودار در هر حرکت متوالی قطب برابر با O(logn+k) است که در آنk تعداد سایتهای درون ناحیهT است که احتمال تغییر در آنها وجود دارد.