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

سال انتشار: 1398
محل انتشار: هفتمین همایش ملی مهندسی رایانه و مدیریت فناوری اطلاعات
کد COI اختصاصی: CSITM07_010
زبان مقاله: فارسی
تعداد مشاهده: 732

نویسندگان

آزمایشگاه تحقیقات و توسعه نرم افزار، دانشکده مهندسی کامپیوتر، دانشگاه تربیت دبیر شهید رجایی

چکیده

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

کلیدواژه ها

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

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.