نمودار قطبي نقاط با قطب متحرك

مسئله نمودار قطبي يكي از تعميم هاي نمودار ورونوي است كه در آن به جاي متر اقليدسي از مقدار زاويه براي محاسبه فاصله استفاده مي شود.. اين مسئله كاربردهاي زيادي در پردازش تصوير، مخابرات و مباحث مربوط به آنتن، رؤيت پذيري و مسيريابي ربات دارد. در سالهاي اخير دو نوع نمودار قطبي مطرح شده و براي انواع سايت ها الگوريتم هاي مناسبي ارائه شده است. همچنين روي همين مسائل با داده هاي جنبشي و حالات پويا الگوريتم هايي ارائه شده است. در اين مقاله قطب به عنوان ناظرمتحرك در نظر گرفته شده و الگوريتمي ارائه مي شود كه مسئله بازسازي نمودار قطبي با قطب نزديك را به صورت كارا و در زمان خطي حل مي كند. در اين حالت زمان پيش پردازش الگوريتم و زمان باز رسم نمودار در هر حركت متوالي قطب برابر با است كه در آن تعداد سايتهاي درون ناحيه است كه احتمال تغيير در آنها وجود دارد.