Art gallery problem
આર્ટ ગેલેરી સમસ્યા અથવા સંગ્રહાલય સમસ્યા એ કોમ્પ્યુટેશનલ ભૂમિતિમાં સારી રીતે અભ્યાસ કરાયેલ દૃશ્યતા સમસ્યા છે. તે નીચેની વાસ્તવિક દુનિયાની સમસ્યામાંથી ઉદ્ભવે છેઃ "એક આર્ટ ગેલેરીમાં, રક્ષકોની ઓછામાં ઓછી સંખ્યા કેટલી હોય છે જે એકસાથે સમગ્ર ગેલેરીનું નિરીક્ષણ કરી શકે?" સમસ્યાના ભૌમિતિક સંસ્કરણમાં, આર્ટ ગેલેરીનું લેઆઉટ એક સરળ બહુકોણ દ્વારા રજૂ થાય છે અને દરેક રક્ષક બહુકોણમાં એક બિંદુ દ્વારા રજૂ થાય છે. બિંદુઓના સમૂહને બહુકોણની રક્ષા કરવા માટે કહેવામાં આવે છે, જો બહુકોણમાં દરેક બિંદુ માટે, કેટલાક એવા હોય કે જે અને વચ્ચેનો રેખાખંડ બહુકોણને છોડતો નથી. આર્ટ ગેલેરીની સમસ્યાને રોબોટિક્સ જેવા ઘણા ક્ષેત્રોમાં લાગુ કરી શકાય છે, જ્યારે આર્ટિફિશિયલ ઇન્ટેલિજન્સ (AI) ને તેમની આસપાસના વાતાવરણને આધારે હલનચલન કરવાની જરૂર હોય છે. અન્ય ક્ષેત્રો, જ્યાં આ સમસ્યા લાગુ કરવામાં આવે છે, તેમાં છબી સંપાદન, તબક્કાની પ્રકાશની સમસ્યાઓ અથવા કુદરતી આફતોની ચેતવણી માટે માળખાગત સુવિધાઓની સ્થાપના સામેલ છે. બે પરિમાણો મૂળ સમસ્યામાં અસંખ્ય ભિન્નતાઓ છે જેને આર્ટ ગેલેરી સમસ્યા તરીકે પણ ઓળખવામાં આવે છે. કેટલીક આવૃત્તિઓમાં રક્ષકો પરિમિતિ સુધી અથવા બહુકોણના શિરોબિંદુઓ સુધી પણ પ્રતિબંધિત હોય છે. કેટલીક આવૃત્તિઓમાં માત્ર પરિમિતિ અથવા પરિમિતિનો સબસેટ સુરક્ષિત રાખવાની જરૂર પડે છે. જે સંસ્કરણમાં રક્ષકોને શિરોબિંદુઓ પર મૂકવા જોઈએ અને માત્ર શિરોબિંદુઓને સુરક્ષિત રાખવાની જરૂર છે તેને ઉકેલવું એ બહુકોણની દૃશ્યતા આલેખ પર પ્રભુત્વ ધરાવતી સમૂહ સમસ્યાને ઉકેલવા સમાન છે. ચાવતાલની આર્ટ ગેલેરી થીયરમ ચાવતાલની આર્ટ ગેલેરી થીયરમ, જેનું નામ વક્લાવ ચાવતાલના નામ પરથી રાખવામાં આવ્યું છે, તે રક્ષકોની ન્યૂનતમ સંખ્યા પર ઉપલી સીમા આપે છે. તે જણાવે છેઃ "શિરોબિંદુઓ સાથે એક સરળ બહુકોણની રક્ષા કરવા માટે, રક્ષકો હંમેશા પૂરતા હોય છે અને કેટલીકવાર જરૂરી હોય છે". ઇતિહાસ કેટલા શિરોબિંદુઓ/ચોકીદારો/રક્ષકોની જરૂર હતી તે પ્રશ્ન 1973માં વિક્ટર ક્લી દ્વારા ચાવતાલ સમક્ષ રજૂ કરવામાં આવ્યો હતો. ત્યારબાદ ટૂંક સમયમાં ચ્વાટલે તે સાબિત કર્યું. ચાવતાલના પુરાવાને પાછળથી સ્ટીવ ફિસ્ક દ્વારા 3-રંગીન દલીલ દ્વારા સરળ બનાવવામાં આવ્યો હતો. ચાવતાલ વધુ ભૌમિતિક અભિગમ ધરાવે છે, જ્યારે ફિસ્ક આલેખ સિદ્ધાંતમાંથી જાણીતા પરિણામોનો ઉપયોગ કરે છે. ફિસ્કનો ટૂંકો પુરાવો સ્ટીવ ફિસ્કનો પુરાવો એટલો ટૂંકો અને ભવ્ય છે કે તેને પ્રૂફ ફ્રોમ ધ બુકમાં સામેલ કરવા માટે પસંદ કરવામાં આવ્યો હતો. સાબિતી નીચે પ્રમાણે છેઃ પ્રથમ, બહુકોણ ત્રિકોણાકાર છે (વધારાના શિરોબિંદુઓ ઉમેર્યા વિના), જે શક્ય છે, કારણ કે ત્રિકોણોનું અસ્તિત્વ ચોક્કસ ચકાસાયેલ પરિસ્થિતિઓમાં સાબિત થાય છે. પરિણામી ત્રિકોણાકાર આલેખના શિરોબિંદુઓ 3-રંગીન હોઈ શકે છે. સ્પષ્ટપણે, 3-રંગ હેઠળ, દરેક ત્રિકોણમાં ત્રણેય રંગો હોવા જોઈએ. કોઈપણ એક રંગ સાથેના શિરોબિંદુઓ માન્ય રક્ષક સમૂહ બનાવે છે, કારણ કે બહુકોણનો દરેક ત્રિકોણ તે રંગ સાથે તેના શિરોબિંદુ દ્વારા સુરક્ષિત હોય છે. ત્રણ રંગો બહુકોણના n શિરોબિંદુઓનું વિભાજન કરે છે, તેથી સૌથી ઓછા શિરોબિંદુઓ સાથેનું રંગ મોટાભાગના રક્ષકો સાથે માન્ય રક્ષક સમૂહને વ્યાખ્યાયિત કરે છે. સાબિતીનું ચિત્રણ સાબિતીને સમજાવવા માટે, આપણે નીચે આપેલા બહુકોણને ધ્યાનમાં લઈએ છીએ. પ્રથમ પગલું એ બહુકોણને ત્રિકોણાકાર કરવાનું છે (આકૃતિ 1 જુઓ). પછી, એક યોગ્ય રંગ (આકૃતિ 2) લાગુ કરે છે અને અવલોકન કરે છે કે ત્યાં લાલ, વાદળી અને લીલા શિરોબિંદુઓ છે. સૌથી ઓછા શિરોબિંદુઓ સાથેનો રંગ વાદળી અથવા લાલ હોય છે, આમ બહુકોણને રક્ષકો દ્વારા આવરી શકાય છે (આકૃતિ 3). આ આર્ટ ગેલેરી પ્રમેય સાથે સંમત થાય છે, કારણ કે બહુકોણમાં શિરોબિંદુઓ હોય છે, અને. સામાન્યીકરણ ચાવતાલની ઉપલી સીમા માન્ય રહે છે જો ખૂણાઓ પર રક્ષકો પરનું પ્રતિબંધ બહુકોણની બહાર ન હોય તેવા કોઈપણ સમયે રક્ષકો માટે ઢીલું કરવામાં આવે. મૂળ કલા-ગેલેરી પ્રમેયની સંખ્યાબંધ અન્ય સામાન્યીકરણ અને વિશેષતાઓ છે. દાખલા તરીકે, ઓર્થોગોનલ બહુકોણ માટે, જેની ધાર/દિવાલો જમણા ખૂણા પર મળે છે, માત્ર રક્ષકોની જરૂર પડે છે. આ પરિણામના ઓછામાં ઓછા ત્રણ અલગ પુરાવા છે, જેમાંથી કોઈ પણ સરળ નથીઃ કાહ્ન, ક્લેવે અને ક્લેઇટમેન દ્વારા; લુબીવ દ્વારા; અને સૅક અને ટૌસસેન્ટ દ્વારા. સંબંધિત સમસ્યા મનસ્વી બહુકોણ ("કિલ્લાની સમસ્યા") ના બાહ્ય ભાગને આવરી લેવા માટે રક્ષકોની સંખ્યા પૂછે છેઃ જો રક્ષકોને બહુકોણની સીમા પર મૂકવામાં આવે તો કેટલીકવાર તે જરૂરી હોય છે અને હંમેશા પૂરતું હોય છે, જ્યારે ક્યારેક તે જરૂરી હોય છે અને જો રક્ષકોને બહુકોણના બાહ્ય ભાગમાં ક્યાંય પણ મૂકવામાં આવે તો હંમેશા પૂરતું હોય છે. બીજા શબ્દોમાં કહીએ તો, અનંત બાહ્ય મર્યાદિત આંતરિક કરતાં આવરી લેવા માટે વધુ પડકારજનક છે. કોમ્પ્યુટેશનલ જટિલતા આર્ટ ગેલેરી સમસ્યાના નિર્ણય સમસ્યાના સંસ્કરણોમાં, એકને બહુકોણ અને સંખ્યા k બંને ઇનપુટ તરીકે આપવામાં આવે છે, અને તે નક્કી કરવું આવશ્યક છે કે બહુકોણને k અથવા ઓછા રક્ષકોથી સુરક્ષિત કરી શકાય છે કે કેમ. આ સમસ્યા-પૂર્ણ છે, જેમ કે તે સંસ્કરણ છે જ્યાં રક્ષકો બહુકોણની ધાર સુધી મર્યાદિત છે. વધુમાં, મોટાભાગની અન્ય પ્રમાણભૂત વિવિધતાઓ (જેમ કે રક્ષક સ્થાનોને શિરોબિંદુઓ સુધી મર્યાદિત કરવા) એન. પી.-સખત હોય છે. રક્ષકોની લઘુતમ સંખ્યા માટે અંદાજિત અલ્ગોરિધમ્સ અંગે, સમસ્યાને એ. પી. એક્સ-હાર્ડ સાબિત કરી, જે સૂચવે છે કે બહુપદી સમય અંદાજિત અલ્ગોરિધમ દ્વારા અમુક નિશ્ચિત અચળાંક કરતાં વધુ સારો કોઈ અંદાજિત ગુણોત્તર પ્રાપ્ત કરી શકાય તેવી શક્યતા નથી. દર્શાવ્યું હતું કે ઇનપુટ બહુકોણને બહિર્મુખ પેટા પ્રદેશોમાં વિભાજીત કરીને અને પછી સમસ્યાને સેટ કવર સમસ્યામાં ઘટાડીને લઘુત્તમ સંખ્યામાં શિરોબિંદુ રક્ષકો માટે લઘુગણક અંદાજ પ્રાપ્ત કરી શકાય છે. બતાવ્યા પ્રમાણે, આર્ટ ગેલેરીની સમસ્યામાંથી મેળવેલ સેટ સિસ્ટમ વી. સી. પરિમાણને બંધાયેલ છે, જે ε-નેટ પર આધારિત સેટ કવર અલ્ગોરિધમ્સના ઉપયોગને મંજૂરી આપે છે, જેનો અંદાજ ગુણોત્તર બહુકોણ શિરોબિંદુઓની સંખ્યાને બદલે રક્ષકોની શ્રેષ્ઠ સંખ્યાનો લઘુગણક છે. અનિયંત્રિત રક્ષકો માટે, સંભવિત રક્ષકોની અનંત સંખ્યા સમસ્યાને વધુ મુશ્કેલ બનાવે છે. જો કે, રક્ષકોને દંડ ગ્રીડ પર મૂકવા માટે પ્રતિબંધિત કરીને, વધુ જટિલ લઘુગણક અંદાજ અલ્ગોરિધમ કેટલીક હળવી વધારાની ધારણાઓ હેઠળ મેળવી શકાય છે, જેમ કે નીચે દર્શાવેલ છે. જો કે, કાર્યક્ષમ અલ્ગોરિધમ્સ મોટા ભાગના શિરોબિંદુ રક્ષકોના સમૂહને શોધવા માટે જાણીતા છે, જે ચ્વાટલના ઉપલા બાઉન્ડ સાથે મેળ ખાય છે. સાબિત કર્યું કે આ રક્ષકો માટે પ્લેસમેન્ટની ગણતરી ઓ (એન લોગ એન) સમયમાં સૌથી ખરાબ સ્થિતિમાં, વિભાજન અને વિજય અલ્ગોરિધમ દ્વારા થઈ શકે છે. તેમણે ફિસ્કના ટૂંકા પુરાવા અને બર્નાર્ડ ચેઝેલના રેખીય સમય સમતલ ત્રિકોણ અલ્ગોરિધમનો ઉપયોગ કરીને રેખીય સમય અલ્ગોરિધમ આપ્યું. છિદ્રો ન ધરાવતા સરળ બહુકોણ માટે, શિરોબિંદુ અને ધાર રક્ષકો માટે સતત પરિબળ અંદાજ અલ્ગોરિધમનું અસ્તિત્વ ઘોષ દ્વારા અનુમાન કરવામાં આવ્યું હતું. ઘોષનું અનુમાન શરૂઆતમાં સરળ બહુકોણના બે વિશેષ પેટા વર્ગોમાં શિરોબિંદુ રક્ષકો માટે સાચું હોવાનું દર્શાવવામાં આવ્યું હતું. મોનોટોન બહુકોણ અને બહુકોણ ધાર પરથી નબળા દેખાય છે. એક અંદાજિત અલ્ગોરિધમ રજૂ કર્યું જે બહુપદી સમયમાં એક મોનોટોન બહુકોણ માટે એક શિરોબિંદુ રક્ષક સમૂહની ગણતરી કરે છે જેમ કે રક્ષક સમૂહનું કદ શિરોબિંદુ રક્ષકોની મહત્તમ સંખ્યા કરતાં 30 ગણું વધારે હોય છે. એક અંદાજિત અલ્ગોરિધમ રજૂ કર્યું જે O (n2) સમયમાં એક સરળ બહુકોણ માટે એક શિરોબિંદુ રક્ષક સમૂહની ગણતરી કરે છે જે ધારથી નબળો દેખાય છે જેમ કે રક્ષક સમૂહનું કદ શિરોબિંદુ રક્ષકોની મહત્તમ સંખ્યા કરતાં 6 ગણું વધારે હોય છે. ત્યારબાદ, શિરોબિંદુ રક્ષકો અને ધાર રક્ષકોનો ઉપયોગ કરીને સામાન્ય સરળ બહુકોણની સુરક્ષા માટે સતત પરિબળ અંદાજ અલ્ગોરિધમ્સ રજૂ કરીને અનુમાનને સંપૂર્ણપણે ઉકેલવાનો દાવો કર્યો હતો. સરળ બહુકોણના પેટા વર્ગની રક્ષા કરતા શિરોબિંદુ માટે, જે ધારથી નબળા દેખાય છે, બહુપદી-સમય અંદાજ યોજના દ્વારા પ્રસ્તાવિત કરવામાં આવી હતી. શિરોબિંદુ રક્ષકો માટે ચોક્કસ અલ્ગોરિધમનો પ્રસ્તાવ મૂકવામાં આવ્યો હતો. લેખકોએ બહુકોણના ઘણા વર્ગો સાથે વ્યાપક ગણતરીના પ્રયોગો હાથ ધર્યા હતા જે દર્શાવે છે કે હજારો શિરોબિંદુઓ સાથે સંકળાયેલા ઉદાહરણો માટે પણ પ્રમાણમાં નાના ગણતરીના સમયમાં શ્રેષ્ઠ ઉકેલો મળી શકે છે. આ ઉદાહરણો માટે ઇનપુટ ડેટા અને શ્રેષ્ઠ ઉકેલો ડાઉનલોડ કરવા માટે ઉપલબ્ધ છે. ત્રણ પરિમાણો જો સંગ્રહાલયને ત્રણ પરિમાણોમાં પોલિહેડ્રોન તરીકે રજૂ કરવામાં આવે, તો પછી દરેક શિરોબિંદુ પર રક્ષક મૂકવાથી એ સુનિશ્ચિત નહીં થાય કે તમામ સંગ્રહાલય નિરીક્ષણ હેઠળ છે. જો કે પોલિહેડ્રોનની તમામ સપાટીનું સર્વેક્ષણ કરવામાં આવશે, કેટલાક પોલિહેડ્રાના આંતરિક ભાગમાં એવા બિંદુઓ છે જે દેખરેખ હેઠળ ન પણ હોય. આર્ટ ગેલેરી સમસ્યાના સંભવિત ઉપયોગના દૃશ્યો આર્ટ ગેલેરી સમસ્યાનો ઉપયોગ બહુવિધ કેમેરાને મૂકવા માટે થઈ શકે છે જ્યારે તેનો ઉદ્દેશ ઓછામાં ઓછા કેમેરાનો ઉપયોગ કરીને કેમેરાની દૃષ્ટિએ મોટા વિસ્તારને આવરી લેવાનો હોય છે. તારા આકારના બહુકોણ સાથે લંબચોરસ બહુકોણને આવરી લેવું પણ જુઓ, બહુકોણનો એક વર્ગ જેના માટે આર્ટ ગેલેરીની સમસ્યાને એક જ રક્ષક સાથે ઉકેલી શકાય છે. પ્રકાશની સમસ્યાઃ જો દિવાલોને પ્રતિબિંબિત કરવામાં આવે તો શું એક જ રક્ષક પૂરતું છે? નોંધો સંદર્ભો સ્ત્રોતો. . . . . . . . . . . . . . . . . . . . . . . . કોમ્પ્યુટેશનલ ભૂમિતિ પુરાવા ધરાવતા લેખો આવરી લેતી સમસ્યાઓ બહુકોણ