Space partitioning
ભૂમિતિમાં, અવકાશ વિભાજન એ સમગ્ર અવકાશ (સામાન્ય રીતે યુક્લિડિયન અવકાશ) ને બે અથવા વધુ અસંબદ્ધ ઉપગણમાં વિભાજિત કરવાની પ્રક્રિયા છે (સમૂહનું વિભાજન પણ જુઓ). બીજા શબ્દોમાં કહીએ તો, જગ્યા વિભાજન જગ્યાને બિન-ઓવરલેપિંગ પ્રદેશોમાં વિભાજિત કરે છે. અવકાશમાં કોઈપણ બિંદુ પછી બરાબર એક પ્રદેશમાં આવેલા હોવાનું ઓળખી શકાય છે. અવકાશ-વિભાજન પ્રણાલીઓ ઘણીવાર અધિક્રમિક હોય છે, જેનો અર્થ થાય છે કે જગ્યા (અથવા અવકાશનો વિસ્તાર) ને ઘણા પ્રદેશોમાં વહેંચવામાં આવે છે, અને પછી તે જ અવકાશ-વિભાજન પ્રણાલી આ રીતે બનાવેલા દરેક પ્રદેશો પર પુનરાવર્તિત રીતે લાગુ કરવામાં આવે છે. પ્રદેશોને વૃક્ષમાં ગોઠવી શકાય છે, જેને અવકાશ-વિભાજન વૃક્ષ કહેવાય છે. મોટાભાગની અવકાશ-વિભાજન પ્રણાલીઓ જગ્યાને વિભાજિત કરવા માટે વિમાનો (અથવા, ઉચ્ચ પરિમાણોમાં, હાયપરપ્લેન) નો ઉપયોગ કરે છેઃ સમતલની એક બાજુના બિંદુઓ એક પ્રદેશ બનાવે છે, અને બીજી બાજુના બિંદુઓ બીજા પ્રદેશની રચના કરે છે. સમતલ પર બરાબર બિંદુઓ સામાન્ય રીતે મનસ્વી રીતે એક અથવા બીજી બાજુ સોંપવામાં આવે છે. આ રીતે વિમાનોનો ઉપયોગ કરીને અવારનવાર જગ્યાનું વિભાજન કરવાથી બી. એસ. પી. વૃક્ષ ઉત્પન્ન થાય છે, જે જગ્યાના વિભાજનના સૌથી સામાન્ય સ્વરૂપોમાંનું એક છે. કોમ્પ્યુટર ગ્રાફિક્સમાં ઉપયોગ કોમ્પ્યુટર ગ્રાફિક્સમાં સ્પેસ પાર્ટીશનિંગ ખાસ કરીને મહત્વનું છે, ખાસ કરીને રે ટ્રેસિંગમાં તેનો ભારે ઉપયોગ થાય છે, જ્યાં તેનો ઉપયોગ વર્ચ્યુઅલ દ્રશ્યમાં વસ્તુઓને ગોઠવવા માટે વારંવાર થાય છે. એક લાક્ષણિક દ્રશ્યમાં લાખો બહુકોણ હોઈ શકે છે. દરેક સાથે કિરણ/બહુકોણ આંતરછેદ પરીક્ષણ કરવું એ ગણતરીની દ્રષ્ટિએ ખૂબ જ ખર્ચાળ કાર્ય હશે. અવકાશ-વિભાજન માહિતી માળખામાં પદાર્થોને સંગ્રહિત કરવાથી (ઉદાહરણ તરીકે કે. ડી. વૃક્ષ અથવા બી. એસ. પી. વૃક્ષ) ચોક્કસ પ્રકારના ભૂમિતિ પ્રશ્નો કરવા માટે તેને સરળ અને ઝડપી બનાવે છે-ઉદાહરણ તરીકે તે નક્કી કરવા માટે કે શું કિરણ પદાર્થને છેદે છે, અવકાશ વિભાજન આંતરછેદ પરીક્ષણની સંખ્યાને પ્રાથમિક કિરણ દીઠ માત્ર થોડા સુધી ઘટાડી શકે છે, જે બહુકોણની સંખ્યાના સંદર્ભમાં લઘુગણક સમયની જટિલતા આપે છે. અવકાશ વિભાજનનો ઉપયોગ ઘણીવાર સ્કેનલાઇન અલ્ગોરિધમ્સમાં પણ થાય છે જેથી કેમેરાના જોવાના ફ્રસ્ટમમાંથી બહુકોણને દૂર કરી શકાય, પાઇપલાઇન દ્વારા પ્રક્રિયા કરાયેલા બહુકોણની સંખ્યાને મર્યાદિત કરી શકાય. અથડામણની શોધમાં પણ એક ઉપયોગ છેઃ બે પદાર્થો એકબીજાની નજીક છે કે કેમ તે નક્કી કરવા માટે જગ્યા વિભાજનનો ઉપયોગ કરીને વધુ ઝડપી થઈ શકે છે. ઇન્ટિગ્રેટેડ સર્કિટ ડિઝાઇનમાં, એક મહત્વપૂર્ણ પગલું ડિઝાઇન નિયમ તપાસ છે. આ પગલું એ સુનિશ્ચિત કરે છે કે પૂર્ણ થયેલ ડિઝાઇન ઉત્પાદનક્ષમ છે. ચેકમાં એવા નિયમોનો સમાવેશ થાય છે જે પહોળાઈ અને અંતર અને અન્ય ભૂમિતિ પેટર્નનો ઉલ્લેખ કરે છે. આધુનિક ડિઝાઇનમાં અબજો બહુકોણ હોઈ શકે છે જે વાયર અને ટ્રાન્ઝિસ્ટરનું પ્રતિનિધિત્વ કરે છે. કાર્યક્ષમ ચકાસણી ભૂમિતિ ક્વેરી પર ભારે આધાર રાખે છે. ઉદાહરણ તરીકે, એક નિયમ સ્પષ્ટ કરી શકે છે કે કોઈપણ બહુકોણ અન્ય કોઈપણ બહુકોણથી ઓછામાં ઓછો n નેનોમીટર દૂર હોવો જોઈએ. આને તમામ બાજુઓ પર n/2 દ્વારા બહુકોણને વિસ્તૃત કરીને અને તમામ છેદતા બહુકોણ શોધવા માટે ક્વેરી દ્વારા ભૂમિતિ ક્વેરીમાં રૂપાંતરિત કરવામાં આવે છે. સંભાવના અને આંકડાકીય શિક્ષણ સિદ્ધાંતમાં અવકાશ વિભાજનમાં ઘટકોની સંખ્યા સંભાવના સિદ્ધાંતમાં કેટલાક પરિણામોમાં કેન્દ્રિય ભૂમિકા ભજવે છે. વધુ વિગતો માટે વૃદ્ધિ કાર્ય જુઓ. ભૂગોળ અને જી. આઈ. એસ. માં ઘણા અભ્યાસો અને ઉપયોગો છે જ્યાં ભૌગોલિક અવકાશી વાસ્તવિકતાને જળશાસ્ત્રીય માપદંડ, વહીવટી માપદંડ, ગાણિતિક માપદંડ અથવા અન્ય ઘણા લોકો દ્વારા વિભાજિત કરવામાં આવે છે. કાર્ટોગ્રાફી અને જીઆઇએસના સંદર્ભમાં-ભૌગોલિક માહિતી પ્રણાલી, પ્રમાણભૂત કોડ દ્વારા પાર્ટીશનના કોષોને ઓળખવા માટે સામાન્ય છે. ઉદાહરણ તરીકે, હાઇડ્રોગ્રાફિક બેસિન અને પેટા-બેસિનને ઓળખતા એચયુસી કોડ માટે, દેશો અને તેના પેટાવિભાગોને ઓળખતા આઇએસઓ <આઇડી1> કોડ, અથવા મનસ્વી ડીજીજી-ચતુર્થાંશ અથવા સ્થાનોને ઓળખતા અલગ વૈશ્વિક ગ્રીડ. ડેટા સ્ટ્રક્ચર્સ સામાન્ય જગ્યા-વિભાજન પ્રણાલીઓમાં નીચેનાનો સમાવેશ થાય છેઃ બી. એસ. પી. વૃક્ષો ક્વાડટ્રીઝ ઓક્ટ્રીઝ કે-ડી વૃક્ષો ડબ્બાઓ આર-વૃક્ષો ઘટકોની સંખ્યા ધારો કે એન-પરિમાણીય યુક્લિડિયન જગ્યા-પરિમાણીય હાયપરપ્લેન દ્વારા વિભાજિત કરવામાં આવે છે. પાર્ટીશનમાં ઘટકોની સંખ્યા કેટલી છે? જ્યારે હાયપરપ્લેન સામાન્ય સ્થિતિમાં હોય ત્યારે સૌથી વધુ ઘટકો પ્રાપ્ત થાય છે, એટલે કે, કોઈ બે સમાંતર નથી અને કોઈ ત્રણનું આંતરછેદ સમાન નથી. ઘટકોની આ મહત્તમ સંખ્યાને આના દ્વારા દર્શાવો. પછી, નીચેનો પુનરાવર્તન સંબંધ આ પ્રમાણે છેઃ-જ્યારે કોઈ પરિમાણો નથી, ત્યારે એક જ બિંદુ છે. - જ્યારે કોઈ હાયપરપ્લેન નથી, ત્યારે બધી જગ્યા એક જ ઘટક છે. અને તેનો ઉકેલ છેઃ જો (ઉદાહરણ તરીકે. લંબરૂપ હાયપરપ્લેન; દરેક વધારાના હાયપરપ્લેન દરેક અસ્તિત્વમાં રહેલા ઘટકને 2 માં વિભાજિત કરે છે). જે આ રીતે ઉપલા-બાઉન્ડેડ છેઃ દ્વિસંગી જગ્યા પાર્ટીશનિંગ ડિસ્ક્રીટ ગ્લોબલ ગ્રીડ બહુકોણ પાર્ટીશન ટેસેલેશન સંદર્ભો કમ્પ્યુટર ગ્રાફિક્સ ભૌમિતિક અલ્ગોરિધમ્સ પણ જુઓ