الگوریتم¬های ابتکاری برای شبه مثلث¬بندی مجموعه نقاط تصادفی در صفحه
محورهای موضوعی :منا نقده فروشها 1 * , فهیمه طاهرخانی 2 , علی نوراله 3
1 - دانشگاه آزاد اسلامی
2 - دانشگاه آزاد اسلامی
3 - دانشگاه آزاد اسلامی
کلید واژه: شبه مثلث¬بندی, پوسته محدب, زنجیره محدب و مقعر, قابلیت رویت, چندضلعی ساده,
چکیده مقاله :
يافتن الگوريتم هايي براي مسائل متنوع مطرح شده در هندسه محاسباتی از جمله مسئله شبه مثلث بندي مجموعه نقاط در صفحه جزو موضوعات علمی است كه تاكنون زمينه فكري دانشمندان علم كامپيوتر را به خود اختصاص داده است. شبه مثلث بندي S که مجموعه-ای از n نقطه در صفحه است، افراز پوسته ي محدب اين مجموعه نقاط از طريق اتصال چندين يال به تعدادي شبه مثلث مي باشد كه همه نقاط را در بر مي گيرد. براي شبه مثلث بندي معيارهاي بهينگي گوناگوني بررسي شده است كه اغلب براساس وزن يال ها و گوشه ها بوده كه در آن شبه مثلث بندي مجموعه نقاط با كمترين وزن يال ها جزو مسائل باز مي باشد. به طور كلي شبه مثلث بندي كمينه به شبه مثلث بندي اطلاق مي شود كه تعداد شبه مثلث هاي ايجاد شده در آن دقيقاً n-2 شبه-مثلث و تعداد كمترين يال هاي مورد نياز در آن 2n-3 يال باشد، همچنين تمامي رئوس يك شبه مثلث بندي كمينه نوك دار مي باشند؛ به اين معني كه در بین تمام زوایای وابسته به آن رئوس، یک زاویه ی بزرگ‌تر از π وجود داشته باشد. هدف اين مقاله ارائه روش‌هایی جديد براي شبه مثلث بندي مجموعه نقاط S در صفحه است تا بتواند تفكرات الگوريتمي جديدي را در اين زمينه باز كند. اين مقاله نشان مي دهد كه ايجاد لايه هايي از پوسته محدب براي مجموعه نقاط و شبه مثلث بندي آن‌ها با دو الگوريتم خاص منجر به توليد شبه مثلث بندي كمينه خواهد شد. همچنين الگوريتمي جديد براي ايجاد يك چندضلعي ساده حلزوني شبه مثلث بندی شده ارائه مي دهد كه توليد چندضلعي هاي ساده تصادفي در دو زمينه مهم كاربردي، شامل بررسي عملكرد الگوريتم ها و ارزيابي زمان پردازنده مورد نياز الگوريتم ها، حائز اهميت مي باشد.
Finding algorithms for the diverse issues proposed in Computational Geometry including pseudo-triangulation of point set is among the scientific subjects, which has already attracted the attention of computer scientists'. A pseudo-triangle is a simple polygon in the plane with exactly three convex vertices, called corners. Three reflex chains of edges join the corners. A pseudo-triangulation for point set is a partition of the convex hull of point set into pseudo-triangles whose vertex set is point set. Many possible optimality criteria have been investigated for pseudo-triangulations which are often based on edge weights or angles in which computing a minimum weight pseudo-triangulation for a point set is among the open problems. A pseudo-triangulation is called minimum if it consists of exactly n-2 pseudo-triangles and the minimum number of edges needed for it is 2n-3. Every vertex of a minimum pseudo-triangulation is pointed. A vertex is pointed if it has an incident angle greater than π. With respect to the proposed cases, the aim of this thesis is to present new methods for pseudo-triangulation of point set in the plane, so that it can open new algorithmic reflections in this field. This research shows that the generation of convex hull layers for point set and their pseudo-triangulation, using two new algorithms which have been considered in this research, minimizes pseudo-triangulation. Also a new algorithm has been considered to generate spiral simple polygon such that the generation of random simple polygons has two main areas of application: testing the correctness and evaluating the CPU-time consumption of algorithms that operate on polygons
[1]. G. Rote, F. Santos, and I. Streinu, “Pseudo-Triangulation – a Survey,” Contemporary Mathematics, 453: 343-410, American Mathematical Society, 2008.
[2]. O. Aichholzer, F. Aurenhammer, H. Krasser, and B. Speckmann, “Convexity minimizes pseudo-triangulations,” Computational Geometry 28, pp.3-10, 2004.
[3]. I. Streinu, “A combinatorial approach to planar non-colliding robot arm motion planning,” In : Proc. 41st Annu.IEEE Sympos. Foundat. Comput.Sci. (FOCS'00), , pp.443-453, 2000.
[4]. S. Gerdjikov, and A. Wolff, “Decomposing a simple polygon into pseudo-triangles and convex polygons,” Computational Geometry 41, pp.21-30, 2008.
[5]. M. Ben-Ner, A. Schulz, and A. Sheffer, “On numbers of pseudo-triangulations,” arXiv: 1210. 7126v1 [cs.CG] 26 oct 2012.
[6]. O. Aichholzer, T. Hackl, and B. Vogtenhuber, “Compatible pointed pseudo-triangulations,” 22nd Canadian Conference on Computational Geometry, 2010.
[7]. M. Pocchiola, and G. Vegter, “Topologically sweeping visibility complexes via pseudo-triangulations,” Discrete Compute.Geom. 16, pp.419-453, 1996.
[8]. M.T. Goodrich, and R. Tamassia, “Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations,” J. Algorithms 23 (1), pp.51-73, 1997.
[9]. D.G. Kirkpatrick, J. Snoeyink, and B. Speckmann, “kinetic collision detection for simple polygons,” Internat. J. Comput. Geom. Appl. 12(1-2), pp. 3-27, 2002.
[10]. B. Speckmann, and C.D. Tόth, “Allocating vertex π-guard in simple polygons via pseudo-triangulations,” Discrete Comput. Geom. 33 (2), pp.345-364, 2005.
[11]. T. Aure, and M. Held, “Heuristic for generation of random polygons,” 8th Canadian Conference On Computational Geometry (CCCG),Ottawa, Canada, pp.38-44,1996.
[12]. D. Dailey, and D. Whitfield, “Constructing random polygons,” SIGITE'08, USA, pp.119-124, 2008.
[13]. M. D. Berg, Computational Geometry: Algorithms and Applications, 3rd edition, published by Springer-Verlag, 2008.
[14]. B. Chazelle, “On the convex layers of a planar Set,” IEEE Tran. Information Theory, Vol. IT-31, No. 4, pp. 509-517, 1985.