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

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

polar diagram of points with moving pole

polar diagram is a generalization of voronoi diagram in which the angle is used as the metric. this problem has many applications in visibility, image processing, telecommunication, antenna, and path planning problems. in recent years two kinds of polar diagram have been proposed and appropriate algorithm have been presented for some types of sites. also, some algorithms has presented for kinetic data and dynamic states. in this paper, it is assumed that the pole is moving and an algorithm is presented that updates near pole polar diagram of sites with moving pole efficiently and in a sub linear time. in this approach, the preprocessing time is 〖o(n^4 log〗_2⁡〖n)〗 and updating time for diagram with each successive movement is 〖 o(log〗_2⁡〖n +k)〗 that k is the number of sites in region t which its site’s regions may be changed