نگارخانه هنری (هندسه). "مسئله نگارخانه هنری" یا "مسئله موزه" یکی از مسائل کار آمدی است که درشاخه هندسه محاسباتی قرار دارد. انگیزهٔ اصلی برای حل این مشکل، حل مشکلی در موزه ها بود به این ترتیب که لازم بود از حداقل تعداد دوربین های امنیتی - که قابلیت چرخش را دارند - برای پوشش دادن کل فضای موزه ها یا نگارخانه های هنری استفاده کرد .
با کمی تغییر در زاویه دید می توان این مسئله را در زمره مسائل هندسه محاسباتی قرار داد . فرض می کنیم که موزه یک چند ضلعی ساده است و هر دوربین، یک نقطه در این چند ضلعی است . مجموعه ای از نقاط در مجموعه S را نقاط جواب مسئله در نظر می گیریم اگر برای هر نقطه مانند p در چند ضلعی q ∈ 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 تا مثلث قبلی می توان دو راس دیگر آن را با یک رنگ دیگر رنگ کرد. و با این روش کل نواحی که تقسیم به مثلث شده بودند با سه رنگ پوشش می یابند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبا کمی تغییر در زاویه دید می توان این مسئله را در زمره مسائل هندسه محاسباتی قرار داد . فرض می کنیم که موزه یک چند ضلعی ساده است و هر دوربین، یک نقطه در این چند ضلعی است . مجموعه ای از نقاط در مجموعه S را نقاط جواب مسئله در نظر می گیریم اگر برای هر نقطه مانند p در چند ضلعی q ∈ 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 تا مثلث قبلی می توان دو راس دیگر آن را با یک رنگ دیگر رنگ کرد. و با این روش کل نواحی که تقسیم به مثلث شده بودند با سه رنگ پوشش می یابند.
wiki: نگارخانه هنری (هندسه)