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

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

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

تاریخچه

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

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

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

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

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

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

نسخه مسئله تصمیم از این مسئله و تمام نسخه‌های دیگر استاندارد این مسئله ان‌پی کامل هستند. این موضوع توسط 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.

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

  1. ↑ «سرقت از لوور؛ آیا یک مسئله ریاضی ۵۰ ساله می‌توانست موزه را امن نگه دارد؟». BBC News فارسی. ۲۰۲۵-۱۱-۰۴. دریافت‌شده در ۲۰۲۵-۱۱-۰۴.
  2. ↑ «Wayback Machine» (PDF). www.researchgate.net. دریافت‌شده در ۲۰۲۵-۱۱-۰۴.
This article is issued from ویکی‌پدیا. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.