نگارخانه هنری (هندسه)

"مسئله نگارخانه هنری" یا "مسئله موزه" یکی از مسائل کار آمدی است که درشاخه هندسه محاسباتی قرار دارد. انگیزهٔ اصلی برای حل این مشکل، حل مشکلی در موزه‌ها بود به این ترتیب که لازم بود از حداقل تعداد دوربین‌های امنیتی-که قابلیت چرخش را دارند-برای پوشش دادن کل فضای موزه‌ها یا نگارخانه‌های هنری استفاده کرد .

با کمی تغییر در زاویه دید می‌توان این مسئله را در زمره مسائل هندسه محاسباتی قرار داد .فرض می کنیم که موزه یک چند ضلعی ساده است و هر دوربین، یک نقطه در این چند ضلعی است . مجموعه‌ای از نقاط در مجموعه S را نقاط جواب مسئله در نظر می گیریم اگر برای هر نقطه مانند p در چند ضلعی$q\in S$ داشته باشیم به‌طوری‌که پاره خط‌های بین p و q از چند ضلعی خارج نشوند.

تاریخچه

ابتدا مسئله نگارخانه هنری توسط Victor Klee در سال ۱۹۷۳ مطرح شد .البته نسخه‌های متعددی از این مسئله وجود دارد که با همین نام شناخته می‌شوند گرچه تفاوت‌هایی دارند . برای مثال در برخی از نسخه‌ها دوربین‌های حفاظتی فقط می‌توانند روی محیط باشند یا روی رئوس چند ضلعی باشند، یا در بعضی نسخ فقط نیاز داریم که محیط یا قسمتی از آن محافظت شوند .

حل کردن این مسئله در حالتی که دوربین‌ها فقط در روی رئوس هستند و فقط لازم است که رئوس محافظت شوند متناظر با حل کردن مسئله dominating set در مبحث Visibility Graph set در چند ضلعی است.

راه حل‌های ارائه شده

تئوری Chvátal’s اشاره می‌کند که به تعداد دوربین کافی و گاهی لازم است که یک چند ضلعی را با n راس بپوشانیم .

آیا این مسئله قابل حل است؟

Kooshesh and Moret یک الگوریتم از (O(n برای حل این مسئله دادند که حد اکثر در رئوس آن دور بین لازم است.

نسخه Decision Problem از این مسئله و تمام نسخه‌های دیگر استاندارد این مسئله ان‌پی کامل هستند .این موضوع توسط Aggarwal و D.T.Leeو A.K.Lin اثبات شده‌است . با توجه به الگوریتم‌های تقریبی (Approxmiation Algorithms Eidenbenz et al.) اثبات کرد که این مسئله جزوه دسته مسائل APX-hard است .

اگر یک موزه را متناظر با یک چند وجهی در مظر بگیریم در این صورت قرار دادن دوربین‌ها در روی رئوس آن لزوماً کافی نیست برای اینکه کل فضای موزه را بپوشانیم چون ممکن است نقاطی در داخل چند وجها باقی بمانند که تحت نظر دوربین‌ها نباشند.

اثبات این قضیه

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

پیوند به بیرون

• بیشتر بدانید
• ویکی‌پدیا

منابع

1. Computational Geometry Course taught by Dave Mount, at the University of Maryland which are copyrighted as follows: Copyright, David M. Mount, 2000, Dept. of Computer Science, University of Maryland, College Park, MD, 20742
2. V. Chvátal. A combinatorial theorem in plane geometry. J. Comb. Theory Series B, 18:39-41, 1975.
3. A. A. Kooshesh and B. M. E. Moret. Three-coloring the vertices of a triangulated simple polygon. Pattern Recognition, 25, 1992.
4. A. Aggarwal. The art gallery problem: Its variations, applications, and algorithmic aspects. PhD thesis, Johns Hopkins University, 1984.
5. D. T. Lee and A. K. Lin. Computational complexity of art gallery problems. IEEE Transactions on Information Theory, 32:276-282, 1986.
6. S. Eidenbenz, C. Stamm, and P. Widmayer. Inapproximability results for guarding polygons and terrains. Algorithmica, 31(1):79-113, 2001.