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

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