نمودار قطبی نقاط با قطب متحرک
محورهای موضوعی : عمومىبهرام صادقی بی غم 1 * , فاطمه ربانی 2
1 - دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه زنجان
2 - دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه تحصیلات تکمیلی علوم پایه زنجان
کلید واژه: نمودار قطبی, نمودار ورونوی, مخابرات, آنتن, زاویه قطبی, رویت پذیری,
چکیده مقاله :
مسئله نمودار قطبی یکی از تعمیم‌های نمودار ورونوی است که در آن به جای متر اقلیدسی از مقدار زاویه برای محاسبه فاصله استفاده می شود.. این مسئله کاربردهای زیادی در پردازش تصویر، مخابرات و مباحث مربوط به آنتن، رؤیت‌پذیری و مسیریابی ربات دارد. در سالهای اخیر دو نوع نمودار قطبی مطرح شده و برای انواع سایت‌ها الگوریتم‌های مناسبی ارائه شده است. همچنین روی همین مسائل با داده‌های جنبشی و حالات پویا الگوریتم‌هایی ارائه شده است. در این مقاله قطب به عنوان ناظرمتحرک در نظر گرفته شده و الگوریتمی ارائه می‌شود که مسئله بازسازی نمودار قطبی با قطب نزدیک را به صورت کارا و در زمان خطی حل می‌کند. در این حالت زمان پیش‌پردازش الگوریتم〖O(n^4 log〗_2〖n)〗 و زمان باز رسم نمودار در هر حرکت متوالی قطب برابر با O(logn+k) است که در آنk تعداد سایتهای درون ناحیهT است که احتمال تغییر در آنها وجود دارد.
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
1.Grima, CI, Márquez, A, and Ortega, L. A locus approach to angle Problems in computational geometry. In Proc. of 14th European Workshop in Computational Geometry, Barcelona, 1998.
2.Grima, CI, Márquez, A, and Ortega, L. Polar diagrams of geometric objects. In 15th European Workshop in Computational Geometry, 1999.
3.Grima, C, Márquez, A, and Ortega, L. Motion Planning and visibility Problems using Polar diagrams. In Annual conference of the European association for computer graphics, EG. Citeseer, 2003.
4.Bigham, B Sadeghi and Mohades, Ali. The dual of Polar diagrams and its extraction. In International Conference of Computational Methods in Sciences and Engineering ICCMSE, vol. 7, PP. 451–454, 2006.
5.Ortega, Lidia M, Rueda, Antonio J, and Feito, Francisco R. A solution to the Path Planning Problem using angle Pre-Processing. Robotics and Autonomous Systems, 58(1):27–36, 2010.
6.Ortega, Lidia and Robles-Ortega, M Dolores. Visibility resolution with Polar diagrams. APPl. Math, 7(5):1651–1669, 2013.
7.Bigham, B Sadeghi and Mohades, Ali. Polar diagram with respect to a near Pole. In 23rd European Workshop on Computational Geometry EWCG07, Austria, PP. 206–209. Citeseer, 2007.
8.Bigham, Bahram Sadeghi, Eskandari, Marzieh, and Tahmasbi, Maryam. Near-Pole Polar diagram of objects and duality. Journal of Computational Science, 3(3):127–131, 2012.
9.Sadeghi Bigham, Bahram, Mohades, Ali, and Ortega, Lidia. Dynamic Polar diagram. Information Processing Letters, 109(2):142–146, 2008.
10.Ehsanfar, Ebrahim, Bigham, Bahram Sadeghi, and Madadi, Najmeh. An optimal solution for dynamic Polar diagram. in CCCG, PP. 51–54, 2010.e
11.Beygi, Mojtaba Nouri and Ghodsi, Mohammad. Polar diagram of moving objects. In 20th Annual Canadian Conference on Computational Geometry, P. 51. Citeseer, 2008.
12.بزاز، زینب، کاربرد دیاگرام ورونوی حساس به زاویه در مسایل بینایی، پایان نامه کارشناسی ارشد، دانشگاه صنعتی امیرکبیر، 1389
13.Aronov, Boris, Edelsbrunner, Herbert, Guibas, Leonidas J., and Sharir, Micha. The number of edges of many faces in a line segment arrangement. Combinatorica, 12(3):261–274, 1992.
14.De Berg, Mark, Cheong, Otfried, van Kreveld, Marc, and Overmars, Mark. Computational geometry. SPringer Berlin Heidelberg, Berlin, third ed., 2008.
15.KirkPatrick, David. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28–35, 1983.
16.Chazelle, Bernard and Dobkin, David P. Intersection of convex objects in two and three dimensions. Journal of the ACM (JACM), 34(1):1–27, 1987.
17.ربانی، فاطمه، دیاگرام قطبی با قطب متحرک. پایان نامه کارشناسی ارشد، دانشگاه تحصیلات تکمیلی علوم پایه زنجان، 1391
18.Sun, Qinbo, et al. "Tacking Control of an Autonomous Sailboat Based on Force Polar Diagram." 2018 13th World Congress on Intelligent Control and Automation (WCICA). IEEE, 2018.
19.The magnetotelluric (MT) method is commonly used to estimate the subsurface conductivity structure.
20.Pranata, Erick, Selvi Misnia Irawati, and Sintia Windhi Niasari. "Magnetotelluric Data Analysis using Swift Skew, Bahr Skew, Polar Diagram, and Phase Tensor: a Case Study in Yellowstone, US."