يافتن الگوريتم هايي براي مسائل متنوع مطرح شده در هندسه محاسباتی از جمله مسئله شبه مثلث بندي مجموعه نقاط در صفحه جزو موضوعات علمی است كه تاكنون زمينه فكري دانشمندان علم كامپيوتر را به خود اختصاص داده است. شبه مثلث بندي S که مجموعه-ای از n نقطه در صفحه است، افراز پوسته ي محدب اين مجموعه نقاط از طريق اتصال چندين يال به تعدادي شبه مثلث مي باشد كه همه نقاط را در بر مي گيرد. براي شبه مثلث بندي معيارهاي بهينگي گوناگوني بررسي شده است كه اغلب براساس وزن يال ها و گوشه ها بوده كه در آن شبه مثلث بندي مجموعه نقاط با كمترين وزن يال ها جزو مسائل باز مي باشد. به طور كلي شبه مثلث بندي كمينه به شبه مثلث بندي اطلاق مي شود كه تعداد شبه مثلث هاي ايجاد شده در آن دقيقاً n-2 شبه-مثلث و تعداد كمترين يال هاي مورد نياز در آن 2n-3 يال باشد، همچنين تمامي رئوس يك شبه مثلث بندي كمينه نوك دار مي باشند؛ به اين معني كه در بین تمام زوایای وابسته به آن رئوس، یک زاویه ی بزرگ‌تر از π وجود داشته باشد. هدف اين مقاله ارائه روش‌هایی جديد براي شبه مثلث بندي مجموعه نقاط S در صفحه است تا بتواند تفكرات الگوريتمي جديدي را در اين زمينه باز كند. اين مقاله نشان مي دهد كه ايجاد لايه هايي از پوسته محدب براي مجموعه نقاط و شبه مثلث بندي آن‌ها با دو الگوريتم خاص منجر به توليد شبه مثلث بندي كمينه خواهد شد. همچنين الگوريتمي جديد براي ايجاد يك چندضلعي ساده حلزوني شبه مثلث بندی شده ارائه مي دهد كه توليد چندضلعي هاي ساده تصادفي در دو زمينه مهم كاربردي، شامل بررسي عملكرد الگوريتم ها و ارزيابي زمان پردازنده مورد نياز الگوريتم ها، حائز اهميت مي باشد. تفاصيل المقالة