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