انجمن کامپیوتر ایران

پيدا کردن مسير ساده از مجموعه نقاط داده شده درون چندضلعي اولين بار توسط چنگ و همکارانش مطرح شد. اين مسئله مي‌تواند در مسيريابي حرکت ربات‌ها، توليد چندضلعي‌هاي تصادفي، طراحي مدارهاي VLSI و غيره کاربرد داشته باشد. در اين مقاله اثبات مي‌کنيم که رسم m زنجيره ساده با طول‌هاي متفاوت داده شده از يک مجموعه نقطه درون يک چندضلعي ساده به‌طوري‌که تمام نقاط را پوشش دهند و زنجيره‌هاي رسم شده باهم تقاطع نداشته باشند ان پي-کامل است. براي اثبات ان پي-کامل بودن اين مسئله، از مسئله «3-پارتيشن» که خود يک مسئله ان پي-کامل است استفاده مي‌کنيم و آن را به مسئله مطرح‌شده کاهش مي‌دهيم. در پايان نيز اثبات مي‌کنيم که رسم يک دورهميلتوني از نقاط درون چندضلعي ساده که لزوماً ساده نيست ان پي- کامل مي‌باشد.