مرکز منطقه ای اطلاع رسانی علوم و فناوری فصلنامه فناوری اطلاعات و ارتباطات ایران 2717-0411 11 41 2020 10 3 Polar Diagram of Points with Moving Pole نمودار قطبی نقاط با قطب متحرک 97 104 fa بهرام صادقی بی غم دانشگاه تحصیلات تکمیلی علوم پایه زنجان فاطمه ربانی دانشگاه تحصیلات تکمیلی علوم پایه زنجان 2020 2 29 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 مسئله نمودار قطبی یکی از تعمیم‌های نمودار ورونوی است که در آن به جای متر اقلیدسی از مقدار زاویه برای محاسبه فاصله استفاده می شود.. این مسئله کاربردهای زیادی در پردازش تصویر، مخابرات و مباحث مربوط به آنتن، رؤیت‌پذیری و مسیریابی ربات دارد. در سالهای اخیر دو نوع نمودار قطبی مطرح شده و برای انواع سایت‌ها الگوریتم‌های مناسبی ارائه شده است. همچنین روی همین مسائل با داده‌های جنبشی و حالات پویا الگوریتم‌هایی ارائه شده است. در این مقاله قطب به عنوان ناظرمتحرک در نظر گرفته شده و الگوریتمی ارائه می‌شود که مسئله بازسازی نمودار قطبی با قطب نزدیک را به صورت کارا و در زمان خطی حل می‌کند. در این حالت زمان پیش‌پردازش الگوریتم〖O(n^4 log〗_2⁡〖n)〗 و زمان باز رسم نمودار در هر حرکت متوالی قطب برابر با O(log⁡n+k) است که در آنk تعداد سایتهای درون ناحیهT است که احتمال تغییر در آنها وجود دارد. http://jour.aicti.ir/en/Article/Download/8683