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

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