الگوریتم تقریبی جدید برای پوشش چندضلعیهای ساده با نواحی ستارهای

چکیده : مسئله پوشش چندضلعی های ساده با کمترین تعداد نواحی ستارهای NP-hard است . بنابراین طراحی الگوریتم های تقریبی در این زمینه از اهمیت بسیاری برخوردار است . تا به حال برای این مسئله الگوریتم تقریبی که فاکتور تقریبش بهتر از n/ 3 باشد طراحی نشده است . ما در این مقاله الگوریتم تقریبی جدیدی با فاکتور تقریب [n / 8] برای مسئله مذکور ارائه کرده ایم که دارای زمان اجرای O(n )3 میباشد .

کلیدواژه ها:

الگوریتم تقریبی ، پوشش چ ندضلعی ها ، مسئله گالری هنری ، نگهبانی نقطهای ، نواحی ستارهای