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