مرتضی خانی دهنوی - مربی، دانشگاه مهندسی فناوری های نوین قوچان،
مهدی خانی دهنوی - دانشجوی دکتری، دانشگاه فردوسی مشهد،
حمید بیدختی - دانشجوی کارشناسی، دانشگاه مهندسی فناوری های نوین قوچان

در این مقاله مساله گالری هنری تشریح و راه حل های موجود برای آن برشمرده می شود. مساله گالری هنری یافتن حداقل تعداد محافظ یا دوربین مورد نیاز جهت محافظت از یک چند ضلعی ساده است. منظور از محافظت این است که هر نقطه در داخل چند ضلعی توسط حداقل یکی از محافظ ها دیده شود. مساله گالری هنری را می توان به صورت یک مساله تصمیم یا یک مساله بهینه سازی در نظر گرفت. این مساله و تمامی نسخه های استاندارد آن ( مانند محدود کردن مکان محافظ ها روی راس ها یا یال ها ) NP-hard است. تلاش هایی برای طراحی الگوریتم تقریبی برای گالری هنری با محافظ های ثابت انجام گرفته است. این الگوریتم ها غالبا براساس اولین الگوریتم ارایه شده توسط آقای Ghosh است. الگوریتم تقریبی بهینه شده آقای Ghosh با تقریب چند جمله ای برای کمترین تعداد محافظ راسی در این گزارش تشریح و ارزیابی شده است.

مساله گالری هنری، محافظت از چند ضلعی، الگوریتم تقریبی، ضریب تقریب