الگوريتم هاي ابتكاري براي شبه مثلث بندي مجموعه نقاط تصادفي در صفحه

يافتن الگوريتم هايي براي مسايل متنوع مطرح شده در هندسه محاسباتي از جمله مسيله شبه مثلث بندي مجموعه نقاط در صفحه جزو موضوعات علمي است كه تاكنون زمينه فكري دانشمندان علم كامپيوتر را به خود اختصاص داده است. شبه مثلث بندي 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.