الگوریتم¬های ابتکاری برای شبه مثلث¬بندی مجموعه نقاط تصادفی در صفحه
الموضوعات :منا نقده فروشها 1 , فهیمه طاهرخانی 2 , علی نوراله 3
1 - دانشگاه آزاد اسلامی
2 - دانشگاه آزاد اسلامی
3 - دانشگاه آزاد اسلامی
الکلمات المفتاحية: شبه مثلث¬بندی, پوسته محدب, زنجیره محدب و مقعر, قابلیت رویت, چندضلعی ساده,
ملخص المقالة :
يافتن الگوريتم هايي براي مسائل متنوع مطرح شده در هندسه محاسباتی از جمله مسئله شبه مثلث بندي مجموعه نقاط در صفحه جزو موضوعات علمی است كه تاكنون زمينه فكري دانشمندان علم كامپيوتر را به خود اختصاص داده است. شبه مثلث بندي S که مجموعه-ای از n نقطه در صفحه است، افراز پوسته ي محدب اين مجموعه نقاط از طريق اتصال چندين يال به تعدادي شبه مثلث مي باشد كه همه نقاط را در بر مي گيرد. براي شبه مثلث بندي معيارهاي بهينگي گوناگوني بررسي شده است كه اغلب براساس وزن يال ها و گوشه ها بوده كه در آن شبه مثلث بندي مجموعه نقاط با كمترين وزن يال ها جزو مسائل باز مي باشد. به طور كلي شبه مثلث بندي كمينه به شبه مثلث بندي اطلاق مي شود كه تعداد شبه مثلث هاي ايجاد شده در آن دقيقاً n-2 شبه-مثلث و تعداد كمترين يال هاي مورد نياز در آن 2n-3 يال باشد، همچنين تمامي رئوس يك شبه مثلث بندي كمينه نوك دار مي باشند؛ به اين معني كه در بین تمام زوایای وابسته به آن رئوس، یک زاویه ی بزرگ‌تر از π وجود داشته باشد. هدف اين مقاله ارائه روش‌هایی جديد براي شبه مثلث بندي مجموعه نقاط S در صفحه است تا بتواند تفكرات الگوريتمي جديدي را در اين زمينه باز كند. اين مقاله نشان مي دهد كه ايجاد لايه هايي از پوسته محدب براي مجموعه نقاط و شبه مثلث بندي آن‌ها با دو الگوريتم خاص منجر به توليد شبه مثلث بندي كمينه خواهد شد. همچنين الگوريتمي جديد براي ايجاد يك چندضلعي ساده حلزوني شبه مثلث بندی شده ارائه مي دهد كه توليد چندضلعي هاي ساده تصادفي در دو زمينه مهم كاربردي، شامل بررسي عملكرد الگوريتم ها و ارزيابي زمان پردازنده مورد نياز الگوريتم ها، حائز اهميت مي باشد.
[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.
