مشاهده مشخصات مقاله
رسم m مسير ساده مجزا از مجموعه نقاط درون چندضلعي ساده در فضاي دوبعدي
|
Authors |
-
عبداله سپه‌وند
-
محمدرضا رزازی
|
|
Conference |
بیست و چهارمین کنفرانس ملی سالانه انجمن کامپیوتر ایران |
|
Abstract |
پيدا کردن مسير ساده از مجموعه نقاط داده شده درون چندضلعي اولين بار توسط چنگ و همکارانش مطرح شد. اين مسئله مي‌تواند در مسيريابي حرکت ربات‌ها، توليد چندضلعي‌هاي تصادفي، طراحي مدارهاي VLSI و غيره کاربرد داشته باشد. در اين مقاله اثبات مي‌کنيم که رسم m زنجيره ساده با طول‌هاي متفاوت داده شده از يک مجموعه نقطه درون يک چندضلعي ساده به‌طوري‌که تمام نقاط را پوشش دهند و زنجيره‌هاي رسم شده باهم تقاطع نداشته باشند ان پي-کامل است. براي اثبات ان پي-کامل بودن اين مسئله، از مسئله «3-پارتيشن» که خود يک مسئله ان پي-کامل است استفاده مي‌کنيم و آن را به مسئله مطرح‌شده کاهش مي‌دهيم. در پايان نيز اثبات مي‌کنيم که رسم يک دورهميلتوني از نقاط درون چندضلعي ساده که لزوماً ساده نيست ان پي- کامل مي‌باشد. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}