مثلث بندی بهینه مجموعه رئوس در صفحه مبتنی بر لایه های محدب

مثلث بندی مجموعه رئوس S در صفحه، برابر است با گراف راست خط بیشین با مجموعه رئوس S، به طوریکه گراف حاصل مسطح باشد هدف از مسئله مثلث بندی با کمترین وزن (MWT)، مثلث بندی مجموعه رئوس S در صفحه است به گونه ای که مجموع طول یال های مثلث بندی کمترین باشد. در سال 2006 ثابت شد که مسئله مثلث بندی بهینه مجموعه رئوس با کمترین وزن NP-Hard است. در این مقاله هدف ارائه دو الگوریتم مکاشفه ای جهت مثلث بندی مجموعه رئوس S در صفحه است به گونه ای که جواب به دست آمده در محدوده جواب بهینه باشد. الگوریتم های مکاشفه ای پیشنهادی، مبتنی بر پوسته های محدب مجموعه رئوس، به صورت تو در تو و لایه ای می باشند و پیچیدگی زمانی مثلث بندی را به طور متوسط کاهش می دهند. پیچیدگی زمانی الگوریتم پیشنهادی دوم در این مقاله به طور متوسط ????? است.

کلیدواژه ها:

مثلث بندی بهینه ، مجموعه رئوس ، پوسته محدب ، الگوریتم مکاشفه ای ، مثلث بندی لایه ای ، پیچیدگی زمانی