بخشی از مقاله
چکیده
رویت پذیری یکی از مسائل معروف و شناخته شده در حوزه هندسه محاسباتی میباشد. در یک چند ضلعی دو نقطه نسبت به هم رویت پذیر هستند هرگاه خط واصل آن دو، به صورت کامل در چندضلعی واقع شود. می گوئیم چندضلعی P توسط گارد نقطه ای x پوشش داده می شود، هرگاه محیط و تمام نقاط داخلی آن توسط x رویت پذیر باشند. گاردها علاوه بر نقطه و رأس می توانند یال، قطر، مسیر و غیره نیز در نظر گرفته شوند و رویت پذیری نسبت به آنها بررسی شود. در این مقاله به معرفی مفهوم گاردهای جفت رأس مجاور می پردازیم و سپس یک کران بالا برای تعداد گاردهای جفت رأس مجاور در چندضلعی های غیرستاره ای ارائه می دهیم.
مقدمه
مفهوم رویت پذیری یکی از مفاهیم پرکاربرد در هندسه محاسباتی می باشد که در حوزه هایی همچون پردازش تصویر، گرافیک کامپیوتری، کنترل ربات و شبکه های کامپیوتری کاربرد دارد. در چندضلعی P دو نقطه p; q 2 P را نسبت به هم رویت پذیر گوئیم اگر خط واصل آن دو، داخل چندضلعی P قرار گیرد. به چندضلعی هایی که تمام فضای آنها توسط نقطه ای مانند x 2 P رویت پذیر باشد، چندضلعی ستاره ای می گوئیم. نقطه x را یک گارد نقطه ای برای چندضلعی P و به مجموعه نقاطی همانند x که تمام چندضلعی از آن نقاط رویت پذیر می باشد، مرکز چندضلعی می گوئیم. بدیهی است اگر مرکز یک چندضلعی تهی باشد، غیرستاره ای است.
یکی از مسائل معروف در حوزه رویت پذیری مسئله موزه هنر می باشد که هدف آن پیدا کردن کمترین تعداد گاردها برای پوشش هر چندضلعی است. Chvatal ]١[ نشان داد که برای هر چندضلعی ساده با n رأس، همواره ⌊ n ⌋ گارد نقطه ای کافی و گاهی لازم می باشد. اگر گاردها قادر به حرکت باشند انواع دیگری از گاردها تعریف می شوند. با فرض حرکت گاردها بر روی یک ضلع، گارد یالی تعریف می شود. گارد یالی، گاردی است که در آن مجموعه تمام نقاط روی یک ضلع به عنوان گارد در نظر گرفته می شود.
نقطه ای مانند p را نسبت به گارد یالی uv رویت پذیر گوئیم اگر نقطه ای مانند q 2 uv وجود داشته باشد که q و p رویت پذیر باشند. یک گارد یالی را بسته گوئیم هرگاه شامل دو نقطه انتهایش باشد، باز گوئیم اگر شامل هیچ یک از نقاط انتهایش نباشد و نیمه باز گوئیم اگر فقط شامل یکی از نقاط انتهایش باشد. انواع مختلف گاردها را می توان در شکل ١ مشاهده کرد. در چندضلعی P یال uv را یک گارد یالی گوئیم هرگاه تمام چندضلعی توسط آن قابل رویت باشد. Toth و همکارانش ]۴[ نشان دادند که هر چندضلعی غیر ستاره ای حداکثر می تواند یک گارد یالی باز داشته باشد. Park و همکارانش ]٣[ نشان دادند که هر چندضلعی غیرستاره ای می تواند حداکثر ٣ گارد یالی بسته داشته باشد. Mukhopadhyay و همکارانش ]٢[ نشان دادند که برای گاردهای یالی نیمه باز نیز این عدد برابر ٣ می باشد.
