Klee's measure problem
કોમ્પ્યુટેશનલ ભૂમિતિમાં, ક્લીની માપ સમસ્યા એ નક્કી કરવાની સમસ્યા છે કે (બહુ-પરિમાણીય) લંબચોરસ શ્રેણીઓના જોડાણના માપની ગણતરી કેટલી અસરકારક રીતે કરી શકાય છે. અહીં, ડી-પરિમાણીય લંબચોરસ શ્રેણીને વાસ્તવિક સંખ્યાઓના ડી અંતરાલોના કાર્ટેશિયન ઉત્પાદન તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જે આરડીનો સબસેટ છે. આ સમસ્યાનું નામ વિક્ટર ક્લીના નામ પરથી રાખવામાં આવ્યું છે, જેમણે અંતરાલોના જોડાણ (કેસ ડી = 1) ની લંબાઈની ગણતરી માટે એક અલ્ગોરિધમ આપ્યું હતું, જે પાછળથી કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંતના અર્થમાં શ્રેષ્ઠ રીતે કાર્યક્ષમ હોવાનું દર્શાવવામાં આવ્યું હતું. 2-પરિમાણીય લંબચોરસ શ્રેણીઓના જોડાણના ક્ષેત્રની ગણતરી કરવાની ગણતરીની જટિલતા પણ હવે જાણીતી છે, પરંતુ કેસ d ≤ 3 એક ખુલ્લી સમસ્યા છે. ઇતિહાસ અને અલ્ગોરિધમ્સ 1977 માં, વિક્ટર ક્લીએ નીચેની સમસ્યાને ધ્યાનમાં લીધીઃ વાસ્તવિક રેખામાં n અંતરાલોના સંગ્રહને જોતાં, તેમના જોડાણની લંબાઈની ગણતરી કરો. ત્યારબાદ તેમણે કોમ્પ્યુટેશનલ જટિલતા (અથવા "રનિંગ ટાઇમ") સાથે આ સમસ્યાને ઉકેલવા માટે એક અલ્ગોરિધમ રજૂ કર્યું-આ નિવેદનના અર્થ માટે બિગ ઓ નોટેશન જુઓ. અંતરાલને ક્રમબદ્ધ કરવા પર આધારિત આ અલ્ગોરિધમ પાછળથી માઈકલ ફ્રેડમેન અને બ્રુસ વેઇડ (1978) દ્વારા શ્રેષ્ઠ હોવાનું દર્શાવવામાં આવ્યું હતું. પાછળથી 1977 માં, જોન બેન્ટલીએ આ સમસ્યાના 2-પરિમાણીય એનાલોગ પર વિચાર કર્યોઃ n લંબચોરસનો સંગ્રહ આપવામાં આવે તો, તેમના જોડાણનું ક્ષેત્ર શોધો. તેમણે એક જટિલતા અલ્ગોરિધમ પણ મેળવ્યું, જે હવે બેન્ટલીના અલ્ગોરિધમ તરીકે ઓળખાય છે, જે સમસ્યાને n-પરિમાણીય સમસ્યાઓમાં ઘટાડવાના આધારે છેઃ આ સમગ્ર વિસ્તારમાં ઊભી રેખા સાફ કરીને કરવામાં આવે છે. આ પદ્ધતિનો ઉપયોગ કરીને, સંઘના વિસ્તારની ગણતરી સ્પષ્ટપણે સંઘની રચના કર્યા વિના કરી શકાય છે. બેન્ટલીનું અલ્ગોરિધમ હવે શ્રેષ્ઠ (2-પરિમાણીય કિસ્સામાં) તરીકે પણ જાણીતું છે, અને તેનો ઉપયોગ અન્ય ક્ષેત્રોમાં કમ્પ્યુટર ગ્રાફિક્સમાં થાય છે. આ બે સમસ્યાઓ વધુ સામાન્ય પ્રશ્નના 1-અને 2-પરિમાણીય કિસ્સાઓ છેઃ nd-પરિમાણીય લંબચોરસ શ્રેણીઓનો સંગ્રહ આપવામાં આવે તો, તેમના જોડાણના માપની ગણતરી કરો. આ સામાન્ય સમસ્યા ક્લીની માપ સમસ્યા છે. જ્યારે ડી-ડાયમેન્શનલ કેસમાં સામાન્યીકૃત કરવામાં આવે છે, ત્યારે બેન્ટલીના અલ્ગોરિધમનો ચાલી રહેલો સમય હોય છે. આ શ્રેષ્ઠ ન હોવાનું બહાર આવ્યું છે, કારણ કે તે માત્ર ડી-પરિમાણીય સમસ્યાને એન (ડી-1)-પરિમાણીય સમસ્યાઓમાં વિઘટિત કરે છે, અને તે પેટા સમસ્યાઓને વધુ વિઘટિત કરતું નથી. 1981માં, જાન વાન લીઉવેન અને ડેરેક વુડે ડાયનેમિક ક્વાડટ્રીઝનો ઉપયોગ કરીને આ અલ્ગોરિધમનો ચાલી રહેલો સમય સુધારીને ડીઓઆર 3 કર્યો હતો. 1988માં, માર્ક ઓવરમાર્સ અને ચી યાપે ડી ≤ 3 માટે એક અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો હતો. તેમનું અલ્ગોરિધમ સમસ્યાને 2-પરિમાણીય ઘટકોમાં વિઘટિત કરવા અને તે ઘટકોને અસરકારક રીતે એકત્રિત કરવા માટે કેડી-ટ્રી જેવી જ ચોક્કસ ડેટા સ્ટ્રક્ચરનો ઉપયોગ કરે છે; 2-પરિમાણીય સમસ્યાઓ પોતે ટ્રેલિસ સ્ટ્રક્ચરનો ઉપયોગ કરીને અસરકારક રીતે હલ કરવામાં આવે છે. બેન્ટલીના અલ્ગોરિધમ કરતાં એસિમ્પ્ટોટિકલી ઝડપી હોવા છતાં, તેના ડેટા સ્ટ્રક્ચર્સ નોંધપાત્ર રીતે વધુ જગ્યાનો ઉપયોગ કરે છે, તેથી તેનો ઉપયોગ ફક્ત એવી સમસ્યાઓમાં થાય છે જ્યાં n અથવા d મોટી હોય. 1998 માં, બોગ્ડન ક્લેબુસે સામાન્ય વિશેષ કેસો માટે સમાન એસિમ્પ્ટોટિક ચાલી રહેલા સમય સાથે સરળ અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો હતો જ્યાં d એ 3 અથવા 4 છે. 2013 માં, ટિમોથી એમ. ચાને એક સરળ અલ્ગોરિધમ વિકસાવ્યું હતું જે ગતિશીલ ડેટા સ્ટ્રક્ચર્સની જરૂરિયાતને ટાળે છે અને લઘુગણક પરિબળને દૂર કરે છે, જે d ≤3 માટે સૌથી વધુ જાણીતા ચાલી રહેલા સમયને ઘટાડે છે. કોઈપણ ડી માટે એકમાત્ર જાણીતી નીચલી બાઉન્ડ છે, અને આ ચાલી રહેલા સમય સાથે શ્રેષ્ઠ અલ્ગોરિધમ્સ ડી = 1 અને ડી = 2 માટે જાણીતા છે. ચાન અલ્ગોરિધમ d ≤ 3 માટે ઉપરની સીમા પૂરી પાડે છે, તેથી d ≤ 3 માટે, તે એક ખુલ્લો પ્રશ્ન રહે છે કે શું ઝડપી અલ્ગોરિધમ્સ શક્ય છે, અથવા વૈકલ્પિક રીતે સખત નીચલી સીમાઓ સાબિત કરી શકાય છે કે કેમ. ખાસ કરીને, તે ખુલ્લું રહે છે કે શું અલ્ગોરિધમનો ચાલી રહેલો સમય d પર આધાર રાખવો જોઈએ. વધુમાં, ત્યાં ઝડપી અલ્ગોરિધમ્સ છે કે જે ખાસ કેસો સાથે વ્યવહાર કરી શકે છે (ઉદાહરણ તરીકે, જ્યારે ઇનપુટ કોઓર્ડિનેટ્સ બાઉન્ડેડ રેન્જમાં પૂર્ણાંકો હોય) તે પ્રશ્ન ખુલ્લો રહે છે. 1ડી ક્લીની માપ સમસ્યા (અંતરાલોના જોડાણ) ને ત્યાં ઉકેલી શકાય છે જ્યાં પી તમામ અંતરાલોને છૂપાવવા માટે જરૂરી વેધન બિંદુઓની સંખ્યાને સૂચવે છે (સામાન્ય બિંદુ દ્વારા વેધન કરેલા અંતરાલોના જોડાણની ગણતરી રેખીય સમયમાં ચરમસીમાની ગણતરી કરીને કરી શકાય છે). પરિમાણ પી એ એક અનુકૂલનશીલ પરિમાણ છે જે ઇનપુટ રૂપરેખાંકન પર આધાર રાખે છે, અને વેધન અલ્ગોરિધમ ક્લીની માપ સમસ્યા માટે અનુકૂલનશીલ અલ્ગોરિધમ આપે છે. કન્વેક્સ વોલ્યુમ અંદાજ પણ જુઓ, જે કન્વેક્સ બોડી સંદર્ભો માટે એક કાર્યક્ષમ અલ્ગોરિધમ છે અને મહત્વપૂર્ણ કાગળો વધુ વાંચે છે. . . . . . . માધ્યમિક સાહિત્ય ફ્રાન્કો પી. પ્રિપેરાટા અને માઈકલ આઈ. શામોસ (1985). કોમ્પ્યુટેશનલ ભૂમિતિ (સ્પ્રિંગર-વેરલેગ, બર્લિન). પ્રોફેસર જેફ એરિકસનની કોમ્પ્યુટેશનલ ભૂમિતિમાં ખુલ્લી સમસ્યાઓની સૂચિમાંથી ક્લીની માપન સમસ્યા. (8 નવેમ્બર, 2005 સુધી પહોંચ્યું, જ્યારે છેલ્લું અપડેટ 31 જુલાઈ, 1998 હતું.) સંદર્ભો કોમ્પ્યુટેશનલ ભૂમિતિ માપન સિદ્ધાંત ગાણિતિક સમસ્યાઓ