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

مساله گالري هنر اين پرسش را مطرح مي کند که چه تعداد نگهبان براي ديدن هر نقطه از چندضلعي کافي است. مجموعه اي از نقاط را در چندضلعي ، مجموعه نگهبان همکار براي گوييم هر گاه مجموعه نگهبانان و گراف رؤيت پذيري مجموعه نگهبانان ، در متصل باشند. در اين مقاله مجموعه جديد را مطرح مي کنيم و به آن k-نگهبان همکار مي¬گوييم، درصورتيکه شرايط زير را داشته باشد: الف) براي هر نقطه در ، نقطه در وجود داشته باشد، بطوريکه از قابل رؤيت باشد. ب) مجموعه گراف رؤيت پذيري متصل باشد. ج) هر نقطه در ، حداقل توسط نقطه ديگر در قابل رؤيت باشد. در اين مقاله ابتدا الگوريتمي براي کاهش تعداد نگهبانان همکار معرفي کرده و نشان مي دهيم که اين الگوريتم براي چندضلعي هاي شانه اي دو سر، مجموعه نگهبانان همکار را به کاهش مي دهد. سپس ثابت مي کنيم که هر n ضلعي حداکثر به نگهبان از مجموعه k-نگهبان همکار نياز دارد.