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

مثلث‌بندي مجموعه نقاط S در صفحه، برابر با تعبيه مسطح يك گراف مسطح مستقيم‌الخط بيشين (با بيشترين يال) روي مجموعه نقاط است به طوري كه مجموعه رئوس گراف دقيقاً همان مجموعه نقاط داده شده باشد. دو مسئله مهم در اين زمينه مورد تحقيق است. الف) به چند طريق مي‌توان مجموعه نقاط S را مثلث‌بندي كرد ب) كدام مثلث‌بندي بر اساس ويژگي خاصي بهينه است. مسئله اول يك مسئله باز است و به جز در شرايط خاص كه داراي رابطه بسته مي‌باشد تا به حال الگوريتمي با زمان چندجمله‌اي براي آن در حالت كلي ارائه نشده است. مسئله دوم نيز در حالتي كه هدف پيداكردن مثلث‌بندي كه مجموع طول يال‌هاي آن كمترين باشد يك مسئله NPHARD است (MWT)، لذا تحقيقات در راستاي ارائه الگوريتم‌هاي مكاشفه‌اي، فرامكاشفه‌اي يا تقريبي براي اين دو حالت انجام شده است. در اين مقاله روشي ارائه شده كه در آن با توليد گراف تقاطع حاصل از تمامي پاره‌خط‌هاي حاصل از تمامي زوج نقاط S توليد مي‌شود و سپس الگوريتم‌هايي براي توليد همه مجموعه‌هاي مستقل بيشين (MIS) گراف تقاطع و همچنين روشي براي شمارش تعداد اين مجموعه‌ها ارائه مي‌شود. اين رويكرد توليد گراف تقاطع و تبديل مسئله مثلث‌بندي به مسئله مجموعه مستقل بيشين نگاهي جديد به مسئله مثلث‌بندي در هر دو حالت الف و ب محسوب مي‌شود و از آنجا كه ارائه الگوريتم براي مسئله الف يا ب به خاطر ذات هندسي‌بودن آن دشوار است لذا با رويكرد مطرح‌شده در اين مقاله، تمامي الگوريتم‌هايي كه تا به حال براي مسئله MIS مطرح شده است را مي‌توان براي حل مسئله مثلث‌بندي در هر دو حالت الف يا ب به كار برد. تكنيك تبديل مسئله مثلث‌بندي به مسئله MIS رويكردي است كه تا به حال روشي مبتني بر آن براي حل مسايل شمارش تعداد طرق مثلث‌بندي يا مثلث‌بندي با كمترين وزن گزارش نشده است. علاوه بر اين يك روش تخميني مكاشفه‌اي براي تعيين متوسط تعداد حالات مثلث‌بندي ارائه خواهد شد كه نتايج پياده‌سازي نشان مي‌دهد روي نمونه‌هايي از ورودي نزديك به مقدار دقيق هستند.