فا   |   En
ورود به سایت
مشاهده‌ مشخصات مقاله

k-نگهبان همکار در گالري هنر

نویسنده (ها)
  • علی آقاکبی
  • علی محدث خراسانی
مربوط به کنفرانس شانزدهمین کنفرانس ملی سالانه انجمن کامپیوتر ایران ‫
چکیده مساله گالري هنر اين پرسش را مطرح مي کند که چه تعداد نگهبان براي ديدن هر نقطه از چندضلعي کافي است. مجموعه اي از نقاط را در چندضلعي ، مجموعه نگهبان همکار براي گوييم هر گاه مجموعه نگهبانان و گراف رؤيت پذيري مجموعه نگهبانان ، در متصل باشند. در اين مقاله مجموعه جديد را مطرح مي کنيم و به آن k-نگهبان همکار مي¬گوييم، درصورتيکه شرايط زير را داشته باشد: الف) براي هر نقطه در ، نقطه در وجود داشته باشد، بطوريکه از قابل رؤيت باشد. ب) مجموعه گراف رؤيت پذيري متصل باشد. ج) هر نقطه در ، حداقل توسط نقطه ديگر در قابل رؤيت باشد. در اين مقاله ابتدا الگوريتمي براي کاهش تعداد نگهبانان همکار معرفي کرده و نشان مي دهيم که اين الگوريتم براي چندضلعي هاي شانه اي دو سر، مجموعه نگهبانان همکار را به کاهش مي دهد. سپس ثابت مي کنيم که هر n ضلعي حداکثر به نگهبان از مجموعه k-نگهبان همکار نياز دارد.
قیمت
  • برای اعضای سایت : ۱٠٠,٠٠٠ ریال
  • برای دانشجویان عضو انجمن : ۲٠,٠٠٠ ریال
  • برای اعضای عادی انجمن : ۴٠,٠٠٠ ریال

خرید مقاله