Art gallery problem
ஆர்ட் கேலரி சிக்கல் அல்லது அருங்காட்சியக சிக்கல் என்பது கணக்கீட்டு வடிவவியலில் நன்கு ஆய்வு செய்யப்பட்ட தெரிவுநிலை சிக்கலாகும். இது பின்வரும் நிஜ உலக சிக்கலில் இருந்து உருவாகிறதுஃ "ஒரு கலைக்கூடத்தில், முழு காட்சியகத்தையும் ஒன்றாக கண்காணிக்கக்கூடிய குறைந்தபட்ச காவலர்களின் எண்ணிக்கை என்ன?" சிக்கலின் வடிவியல் பதிப்பில், ஆர்ட் கேலரியின் தளவமைப்பு ஒரு எளிய பலகோணத்தால் குறிக்கப்படுகிறது மற்றும் ஒவ்வொரு காவலும் பலகோணத்தில் ஒரு புள்ளியால் குறிக்கப்படுகிறது. பலகோணத்தில் உள்ள ஒவ்வொரு புள்ளிக்கும், மற்றும் இடையே உள்ள கோடு பிரிவு பலகோணத்தை விட்டு வெளியேறாத வகையில் இருந்தால், புள்ளிகளின் தொகுப்பு ஒரு பலகோணத்தைப் பாதுகாப்பதாகக் கூறப்படுகிறது. ஆர்ட் கேலரி சிக்கலை ரோபாட்டிக்ஸ் போன்ற பல களங்களில் பயன்படுத்தலாம், செயற்கை நுண்ணறிவு (AI) அவற்றின் சுற்றுப்புறங்களைப் பொறுத்து இயக்கங்களைச் செய்ய வேண்டியிருக்கும். இந்த சிக்கல் பயன்படுத்தப்படும் பிற களங்கள், பட எடிட்டிங், ஒரு கட்டத்தின் லைட்டிங் சிக்கல்கள் அல்லது இயற்கை பேரழிவுகள் பற்றிய எச்சரிக்கைக்காக உள்கட்டமைப்புகளை நிறுவுதல் ஆகியவற்றில் உள்ளன. இரண்டு பரிமாணங்கள் அசல் சிக்கலின் பல மாறுபாடுகள் உள்ளன, அவை ஆர்ட் கேலரி சிக்கல் என்றும் குறிப்பிடப்படுகின்றன. சில பதிப்புகளில் காவலர்கள் சுற்றளவு அல்லது பலகோணத்தின் செங்குத்துகளுக்கு கூட கட்டுப்படுத்தப்படுகின்றன. சில பதிப்புகளில் சுற்றளவு அல்லது சுற்றளவின் துணைக்குழு மட்டுமே பாதுகாக்கப்பட வேண்டும். காவலர்கள் செங்குத்துகளில் வைக்கப்பட வேண்டும் மற்றும் செங்குத்துகள் மட்டுமே பாதுகாக்கப்பட வேண்டும் என்ற பதிப்பைத் தீர்ப்பது பலகோணத்தின் தெரிவுநிலை வரைபடத்தில் ஆதிக்கம் செலுத்தும் தொகுப்பு சிக்கலைத் தீர்ப்பதற்கு சமம். சாவட்டாலின் ஆர்ட் கேலரி தேற்றம் சாவட்டாலின் ஆர்ட் கேலரி தேற்றம், வக்லாவ் சாவட்டாலின் பெயரால் பெயரிடப்பட்டது, குறைந்தபட்ச எண்ணிக்கையிலான காவலர்களுக்கு மேல் வரம்பைக் கொடுக்கிறது. அது கூறுகிறதுஃ "செங்குத்துகளுடன் கூடிய ஒரு எளிய பலகோணத்தைப் பாதுகாக்க, காவலர்கள் எப்போதும் போதுமானவை மற்றும் சில நேரங்களில் அவசியமானவை". எத்தனை செங்குத்துகள்/காவலர்கள்/காவலர்கள் தேவை என்ற கேள்வி 1973 ஆம் ஆண்டில் விக்டர் க்ளீ என்பவரால் சாவட்டலுக்கு முன்வைக்கப்பட்டது. சிறிது காலத்திற்குப் பிறகு சாவடல் அதை நிரூபித்தார். சாவட்டாலின் ஆதாரம் பின்னர் ஸ்டீவ் ஃபிஸ்கால் 3-வண்ண வாதம் மூலம் எளிமைப்படுத்தப்பட்டது. சாவடல் அதிக வடிவியல் அணுகுமுறையைக் கொண்டுள்ளது, அதே நேரத்தில் ஃபிஸ்க் வரைபடக் கோட்பாட்டின் நன்கு அறியப்பட்ட முடிவுகளைப் பயன்படுத்துகிறது. ஸ்டீவ் ஃபிஸ்கின் ஆதாரம் மிகவும் குறுகியதாகவும் நேர்த்தியாகவும் இருப்பதால், புத்தகத்திலிருந்து ஆதாரங்களில் சேர்ப்பதற்காக இது தேர்ந்தெடுக்கப்பட்டது. ஆதாரம் பின்வருமாறு செல்கிறதுஃ முதலாவதாக, பலகோணம் முக்கோணமாக உள்ளது (கூடுதல் செங்குத்துகளைச் சேர்க்காமல்), இது சாத்தியமாகும், ஏனெனில் முக்கோணங்களின் இருப்பு சில சரிபார்க்கப்பட்ட நிலைமைகளின் கீழ் நிரூபிக்கப்பட்டுள்ளது. இதன் விளைவாக வரும் முக்கோண வரைபடத்தின் உச்சிகள் 3-நிறமாக இருக்கலாம். தெளிவாக, ஒரு 3-நிறத்தின் கீழ், ஒவ்வொரு முக்கோணமும் மூன்று வண்ணங்களையும் கொண்டிருக்க வேண்டும். எந்தவொரு ஒரு நிறத்தையும் கொண்ட செங்குத்துகள் ஒரு செல்லுபடியாகும் பாதுகாப்பு தொகுப்பை உருவாக்குகின்றன, ஏனெனில் பலகோணத்தின் ஒவ்வொரு முக்கோணமும் அதன் உச்சியால் அந்த நிறத்துடன் பாதுகாக்கப்படுகிறது. மூன்று வண்ணங்கள் பலகோணத்தின் n செங்குத்துகளைப் பிரிப்பதால், மிகக் குறைந்த செங்குத்துகளைக் கொண்ட நிறம் பெரும்பாலான காவலர்களுடன் செல்லுபடியாகும் பாதுகாப்பு அமைப்பை வரையறுக்கிறது. ஆதாரத்தின் விளக்கப்படம் ஆதாரத்தை விளக்குவதற்கு, கீழே உள்ள பலகோணத்தை நாம் கருத்தில் கொள்கிறோம். முதல் படி பலகோணத்தை முக்கோணமாக்குவதாகும் (படம் 1 ஐப் பார்க்கவும்). பின்னர், ஒருவர் சரியான நிறத்தைப் பயன்படுத்துகிறார் (படம் 2) மற்றும் சிவப்பு, நீலம் மற்றும் பச்சை செங்குத்துகள் இருப்பதை கவனிக்கிறார். மிகக் குறைந்த செங்குத்துகளைக் கொண்ட நிறம் நீலம் அல்லது சிவப்பு, எனவே பலகோணத்தை காவலர்களால் மூட முடியும் (படம் 3). இது ஆர்ட் கேலரி தேற்றத்துடன் உடன்படுகிறது, ஏனெனில் பலகோணத்திற்கு செங்குத்துகள் உள்ளன, மற்றும். பலகோணத்திற்கு வெளியே இல்லாத எந்த நேரத்திலும் மூலைகளில் உள்ள காவலர்களுக்கான கட்டுப்பாடு காவலர்களுக்கு தளர்த்தப்பட்டால் சாவட்டாலின் மேல் எல்லை செல்லுபடியாகும். அசல் கலை-கேலரி தேற்றத்தின் பல பொதுமைப்படுத்தல்கள் மற்றும் நிபுணத்துவங்கள் உள்ளன. உதாரணமாக, ஆர்த்தோகனல் பலகோணங்களுக்கு, அவற்றின் விளிம்புகள்/சுவர்கள் சரியான கோணங்களில் சந்திக்கும், காவலர்கள் மட்டுமே தேவை. இந்த முடிவுக்கு குறைந்தது மூன்று தனித்துவமான சான்றுகள் உள்ளன, அவற்றில் எதுவும் எளிமையானவை அல்லஃ கான், க்ளோவ் மற்றும் க்ளைட்மேன்; லுபிவ்; மற்றும் சாக் மற்றும் டௌஸ்சைண்ட். ஒரு தொடர்புடைய சிக்கல் ஒரு தன்னிச்சையான பலகோணத்தின் ("கோட்டை சிக்கல்") வெளிப்புறத்தை மறைக்க காவலர்களின் எண்ணிக்கையைக் கேட்கிறதுஃ பலகோணத்தின் எல்லையில் காவலர்கள் வைக்கப்பட்டால் அவை சில நேரங்களில் அவசியமானவை மற்றும் எப்போதும் போதுமானவை, அதே நேரத்தில் சில நேரங்களில் அவசியமானவை மற்றும் எப்போதும் போதுமானவை பலகோணத்தின் வெளிப்புறத்தில் எங்கும் காவலர்கள் வைக்கப்பட்டால். வேறு வார்த்தைகளில் கூறுவதானால், வரையறுக்கப்பட்ட உட்புறத்தை விட எல்லையற்ற வெளிப்புறத்தை மறைப்பது மிகவும் சவாலானது. கணக்கீட்டு சிக்கலானது ஆர்ட் கேலரி சிக்கலின் முடிவு சிக்கல் பதிப்புகளில், ஒன்று ஒரு பலகோணம் மற்றும் ஒரு எண் k ஆகிய இரண்டையும் உள்ளீடாக வழங்கப்படுகிறது, மேலும் பலகோணத்தை k அல்லது குறைவான காவலர்களால் பாதுகாக்க முடியுமா என்பதை தீர்மானிக்க வேண்டும். இந்த சிக்கல்-முழுமையானது, அதே போல் காவலர்கள் பலகோணத்தின் விளிம்புகளுக்கு கட்டுப்படுத்தப்பட்ட பதிப்பாகும். மேலும், பெரும்பாலான பிற நிலையான மாறுபாடுகள் (பாதுகாப்பு இருப்பிடங்களை செங்குத்துகளுக்கு கட்டுப்படுத்துவது போன்றவை) NP-கடினமானவை. குறைந்தபட்ச எண்ணிக்கையிலான காவலர்களுக்கான தோராயமான வழிமுறைகளைப் பொறுத்தவரை, சிக்கலை ஏபிஎக்ஸ்-கடினமானது என்று நிரூபித்தது, இது ஒரு பல்லுறுப்புக்கோவை நேர தோராயமான வழிமுறையால் சில நிலையான மாறிலியை விட சிறந்த தோராய விகிதத்தை அடைய முடியாது என்பதைக் குறிக்கிறது. உள்ளீட்டு பலகோணத்தை குவிந்த துணைப் பகுதிகளாக வேறுபடுத்தி, பின்னர் சிக்கலை ஒரு செட் கவர் சிக்கலாகக் குறைப்பதன் மூலம் குறைந்தபட்ச எண்ணிக்கையிலான வெர்டெக்ஸ் கார்டுகளுக்கு ஒரு மடக்கை தோராயமாக அடைய முடியும் என்பதைக் காட்டியது. காட்டியபடி, ஒரு ஆர்ட் கேலரி சிக்கலில் இருந்து பெறப்பட்ட செட் அமைப்பு வி. சி பரிமாணத்தை வரம்புக்குட்பட்டது, இது ε-நெட்டுகளின் அடிப்படையில் செட் கவர் வழிமுறைகளைப் பயன்படுத்த அனுமதிக்கிறது, அதன் தோராயமான விகிதம் பலகோண செங்குத்துகளின் எண்ணிக்கையை விட உகந்த எண்ணிக்கையிலான காவலர்களின் மடக்கைக் குறிக்கிறது. கட்டுப்பாடற்ற காவலர்களைப் பொறுத்தவரை, எண்ணற்ற எண்ணிக்கையிலான சாத்தியமான காவலர் நிலைகள் சிக்கலை இன்னும் கடினமாக்குகின்றன. இருப்பினும், காவலர்கள் ஒரு சிறந்த கட்டத்தில் படுத்துக் கொள்வதைக் கட்டுப்படுத்துவதன் மூலம், சில லேசான கூடுதல் அனுமானங்களின் கீழ் மிகவும் சிக்கலான மடக்கை தோராயமான வழிமுறையைப் பெறலாம். இருப்பினும், திறமையான வழிமுறைகள் பெரும்பாலான வெர்டெக்ஸ் கார்டுகளின் தொகுப்பைக் கண்டுபிடிப்பதில் அறியப்படுகின்றன, இது ச்வாடலின் மேல் எல்லைக்கு பொருந்துகிறது. இந்த காவலர்களுக்கான இடம் O (n log n) நேரத்தில் மிக மோசமான நிலையில், வகுத்தல் மற்றும் கைப்பற்றுதல் வழிமுறை மூலம் கணக்கிடப்படலாம் என்பதை நிரூபித்தது. ஃபிஸ்கின் குறுகிய ஆதாரம் மற்றும் பெர்னார்ட் சாஸெல்லின் நேரியல் நேர விமான முக்கோண வழிமுறையைப் பயன்படுத்தி ஒரு நேரியல் நேர வழிமுறையை வழங்கினார். துளைகள் இல்லாத எளிய பலகோணங்களுக்கு, உச்சி மற்றும் விளிம்பு காவலர்களுக்கான நிலையான காரணி தோராயமான வழிமுறை இருப்பதை கோஷ் ஊகித்தார். கோஷின் அனுமானம் ஆரம்பத்தில் எளிய பலகோணங்களின் இரண்டு சிறப்பு துணை வகைகளில் உள்ள உச்சி காவலர்களுக்கு உண்மை என்று காட்டப்பட்டது, அதாவது. மோனோடோன் பலகோணங்கள் மற்றும் பலகோணங்கள் ஒரு விளிம்பில் இருந்து பலவீனமாகத் தெரியும். ஒரு மோனோடோன் பலகோணத்திற்கான ஒரு வெர்டெக்ஸ் காவலர் தொகுப்பை பல்லுறுப்புக்கோவை நேரத்தில் கணக்கிடும் ஒரு தோராயமான வழிமுறையை வழங்கினார், அதாவது காவலர் தொகுப்பின் அளவு வெர்டெக்ஸ் காவலர்களின் உகந்த எண்ணிக்கையை விட 30 மடங்கு அதிகமாக இருக்கும். O (n2) நேரத்தில் கணக்கிடும் ஒரு தோராயமான வழிமுறையை வழங்கினார், இது ஒரு எளிய பலகோணத்திற்கான ஒரு வெர்டெக்ஸ் காவலர் தொகுப்பாகும், இது ஒரு விளிம்பில் இருந்து பலவீனமாகத் தெரியும், அதாவது காவலர் தொகுப்பின் அளவு வெர்டெக்ஸ் காவலர்களின் உகந்த எண்ணிக்கையை விட 6 மடங்கு அதிகமாக இருக்கும். அதைத் தொடர்ந்து, வெர்டெக்ஸ் கார்டுகள் மற்றும் எட்ஜ் கார்டுகளைப் பயன்படுத்தி பொதுவான எளிய பலகோணங்களைப் பாதுகாப்பதற்கான நிலையான காரணி தோராய வழிமுறைகளை வழங்குவதன் மூலம் அனுமானத்தை முழுமையாகத் தீர்த்ததாகக் கூறப்படுகிறது. ஒரு விளிம்பில் இருந்து பலவீனமாகத் தெரியும் எளிய பலகோணங்களின் துணைப்பிரிவைப் பாதுகாக்கும் உச்சிக்கு, ஒரு பல்லுறுப்புக்கோவை-நேர தோராய திட்டம் முன்மொழியப்பட்டது. வெர்டெக்ஸ் கார்டுகளுக்கு ஒரு சரியான வழிமுறை முன்மொழியப்பட்டது. ஆயிரக்கணக்கான செங்குத்துகளுடன் தொடர்புடைய நிகழ்வுகளுக்கு கூட ஒப்பீட்டளவில் சிறிய கணக்கீட்டு நேரங்களில் உகந்த தீர்வுகளைக் காணலாம் என்பதைக் காட்டும் பல வகை பலகோணங்களுடன் விரிவான கணக்கீட்டு சோதனைகளை ஆசிரியர்கள் நடத்தினர். உள்ளீட்டு தரவு மற்றும் இந்த நிகழ்வுகளுக்கான உகந்த தீர்வுகள் பதிவிறக்கத்திற்கு கிடைக்கின்றன. மூன்று பரிமாணங்கள் ஒரு அருங்காட்சியகம் மூன்று பரிமாணங்களில் ஒரு பாலிஹெட்ரானாக குறிப்பிடப்பட்டால், ஒவ்வொரு முனையிலும் ஒரு காவலரை வைப்பது அருங்காட்சியகம் முழுவதும் கண்காணிப்பில் இருப்பதை உறுதி செய்யாது. பாலிஹெட்ரானின் அனைத்து மேற்பரப்பும் கணக்கெடுக்கப்பட்டாலும், சில பாலிஹெட்ராவுக்கு உட்புறத்தில் கண்காணிப்பின் கீழ் இல்லாத புள்ளிகள் உள்ளன. ஆர்ட் கேலரி சிக்கலின் சாத்தியமான பயன்பாட்டு காட்சிகள் குறைந்தபட்ச எண்ணிக்கையிலான கேமராக்களைப் பயன்படுத்தி, கேமராக்களின் பார்வையில் ஒரு பெரிய பகுதியை மறைக்கும் நோக்கமாக இருக்கும்போது, பல கேமராக்களை வைக்க ஆர்ட் கேலரி சிக்கலைப் பயன்படுத்தலாம். மேலும் பார்க்கவும் நட்சத்திர பலகோணங்களுடன் ஒரு செவ்வக பலகோணத்தை மூடுவது நட்சத்திர வடிவ பலகோணங்கள், ஆர்ட் கேலரி சிக்கலை ஒற்றை பாதுகாப்பு மூலம் தீர்க்கக்கூடிய பலகோணத்தின் ஒரு வகுப்பு. ஒளிரும் சிக்கல்ஃ சுவர்கள் பிரதிபலிக்கப்பட்டால் ஒரு காவலர் போதுமா? குறிப்புகள் குறிப்பு ஆதாரங்கள். . . . . . . . . . . . . . . . . . . . . . . . கணக்கீட்டு வடிவியல் சான்றுகளைக் கொண்ட கட்டுரைகள் சிக்கல்களை உள்ளடக்கிய பலகோணங்கள்