مریم طهماسبی - استادیار و مدیر گروه علوم کامپیوتر دانشکده علوم ریاضی دانشگاه شهید بهشتی تهران
قادر ایمانی - دانشجوی کارشناسی ارشد علوم کامپیوتر دانشگاه شهید بهشتی تهران
ابراهیم امینی فر - دانشجوی کارشناسی دانشگاه نبی اکرم

مساله گالری هنری از جمله مسائل کلاسیک مطرح در هندسه محاسباتی می باشد، این مساله در طول سالیان دراز موردتوجه ریاضیدانان واندیشمندان زیادی قرار گرفته و لذا آنها سعی کرده اند مساله گالری هنری را از ابعاد و زوایای گوناگون مورد بررسی قرار دهند مساله گالریهنری دارای زمینه های کاربردی بسیاری درزمینه سیستم های حفاظتی ، دوربین های مداربسته ، طراحی انیمیشن ، سر گرمی های رایانه ای، برنامه نویسی بازی های کامپیوتری ، برنامه نویسی رباتیک و بسیاری از مسائل گرافیکی می باشد که در همه موارد مذکور سوال اصلی ناحیهتحت پوشش یک نقطه یا بطور خاص تر ناحیه پوششی یک دوربین مداربسته می باشد. ناحیه پوششی یک دوربین در مورد سیستم هایحفاظتی و امنیتی در مراکز امنیتی و نظامی و همچنین در مورد کاربردهای گرافیکی (ناحیه قابل دید یا قابل پوشش یک شخصیت گرافیکی،که با این الگوریتم حداکثر مساحت تحت پوشش شخصیت انیمیشنی تعیین می شود) کاربرد دارد. در این مقاله یک الگوریتم جدید برای پیداکردن ناحیه پوششی یک چندضلعی که یک دوربین داخل آن کار گذاشته شده است مورد بررسی قرار گرفته است،الگوریتم ارایه شده ازابزارهای جدیدی برای پیمایش چندضلعی و انجام الگوریتم استفاده می کند، ابتدا این الگوریتم در 4 مرحله شرح داده شده است و سپسدرستی الگوریتم بررسی و مورد توجه قرار گرفته است، سپس این الگوریتم برای حالت چندضلعی که دارای منحنی (چندضلعی های قوس دار) و سپس برای چندضلعی حفره دار بررسی می شود. پیچیدگی زمانی این الگوریتم طرح شده از مرتبه (O(n ognl می باشد که نشان می دهد این الگوریتم از نظر زمانی در وضعیت بهینه قرار دارد و نسبت به الگوریتم های ارایه شده قبلی بهبود یافته است.

مساله گالری هنری -چند ضلعی محدب – ناحیه پوششی – خط جاروب – نقطه پیشامد- صف پیشامد- چندضلعی حفره دار-چندضلعی قوسدار