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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

با کمی تغییر در زاویه دید می‌توان این مساله را در زمره مسائل هندسه محاسباتی قرار داد .فرض می کنیم که موزه یک چند ضلعی ساده است و هر دوربین، یک نقطه در این چند ضلعی است . مجموعه‌ای از نقاط در مجموعه 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.