نمودار قطبی نقاط با قطب متحرک

مسئله نمودار قطبی یکی از تعمیم های نمودار ورونوی است که در آن به جای متر اقلیدسی از مقدار زاویه برای محاسبه فاصلهاستفاده می شود. این مسئله کاربردهای زیادی در پردازش تصویر، مخابرات و مباحث مربوط به آنتن، رویت پذیری و مسیریابیربات دارد. در سالهای اخیر دو نوع نمودار قطبی مطرح شده و برای انواع سایت ها الگوریتم های مناسبی ارائه شده است.همچنین روی همین مسائل با داده های جنبشی و حالات پویا الگوریتم هایی ارائه شده است. در این مقاله قطب به عنوانناظرمتحرک در نظر گرفته شده و الگوریتمی ارائه می شود که مسئله بازسازی نمودار قطبی با قطب نزدیک را به صورت کارا ودر زمان خطی حل می کند. در این حالت زمان پیش پردازش الگوریتم (O(n(۴)log(۲)n) و زمان باز رسم نمودار در هر حرکتمتوالی قطب برابر با (O(log n+k است که در آن k تعداد سایت های درون ناحیه T است که احتمال تغییر در آنها وجود دارد.

کلیدواژه ها:

نمودار قطبی ، نمودار ورونوی ، مخابرات ، آنتن ، زاویه قطبی ، رویت پذیری