Kinetic closest pair
ગતિશીલ સૌથી નજીકની જોડી માહિતી માળખું એ ગતિશીલ માહિતી માળખું છે જે બિંદુઓની સૌથી નજીકની જોડી જાળવે છે, જે મેટ્રિક જગ્યામાં સમય સાથે સતત આગળ વધી રહેલા n બિંદુઓના સમૂહ P ને આપવામાં આવે છે. જ્યારે સ્થિર કિસ્સામાં ઘણા કાર્યક્ષમ અલ્ગોરિધમ્સ જાણીતા હતા, ત્યારે તેઓ ગતિમાન કરવા માટે મુશ્કેલ સાબિત થયા હતા, તેથી આ સમસ્યાને ઉકેલવા માટે નવા સ્થિર અલ્ગોરિધમ્સ વિકસાવવામાં આવ્યા હતા. 2D કેસ અભિગમ 1 સૌથી નજીકની જોડીની જાળવણી માટેનો સૌથી સરળ ગતિ અભિગમ એ છે કે ડેલાઉને ત્રિકોણના પ્રકારોનો ઉપયોગ કરવો. ષટ્કોણનો વિચાર કરો અને તેને છ સમબાહુ ત્રિકોણમાં વિભાજીત કરો, અને પછી દરેક સમબાહુ ત્રિકોણના આધારે ડેલાઉને ત્રિકોણ બનાવો, કારણ કે દરેક એક બહિર્મુખ આકાર છે. આ છ ડેલાઉને ત્રિકોણોનું જોડાણ, જેને સમબાહુ ડેલાઉને આલેખ (ઈડીજી) કહેવામાં આવે છે, તે નજીકના પડોશી આલેખ (એન. એન. જી.) માટે સુપરગ્રાફ છે; ઈડીજીમાં લઘુત્તમ લંબાઈ સાથે ધારના અંતિમ બિંદુઓ સૌથી નજીકની જોડી આપે છે. બહિર્મુખ આકારોના આધારે ડેલાઉને ત્રિકોણ જાળવવાનું સરળ છે. સમય જતાં ઇ. ડી. જી. ને જોતાં, ઇ. ડી. જી. ની ધાર પર કાઇનેટિક ટુર્નામેન્ટ ટ્રી બનાવીને, કોઈ પણ વ્યક્તિ સરળતાથી સૌથી નજીકની જોડી જાળવી શકે છે. આ સૌથી નજીકની જોડી કે. ડી. એસ. કાર્યક્ષમ, ઋણમુક્ત પ્રતિભાવશીલ અને સઘન છે, પરંતુ સામાન્ય રીતે સ્થાનિક નથી. નીચેનો અભિગમ નજીકના જોડીની જાળવણી માટે સ્થાનિક કે. ડી. એસ. રજૂ કરે છે. અભિગમ 2 બીજો ગતિશીલ અભિગમ નીચેના અવલોકનો પર આધારિત છે. વિભાજીત કરો અને જીતી લો જો કોઈ બિંદુની આસપાસની જગ્યાને કોણીય રીતે છ "વેજ" માં વહેંચવામાં આવે, દરેક પહોળું હોય, તો દરેક વેજમાં સૌથી નજીકનું બિંદુ સૌથી નજીકનું બિંદુ હોય છે. આ લેખનો બાકીનો ભાગ "મુખ્ય" પાંખડીઓ (જે x-અક્ષ દ્વારા દ્વિભાજિત થાય છે) પર ધ્યાન કેન્દ્રિત કરશે, અને સમતલને આ રીતે ફેરવ્યા પછી અન્ય પાંખડીઓ પર સપ્રમાણ દલીલો લાગુ થશે. મેળ ખાતા પોઇન્ટ્સ અને જો તેઓ એકબીજાની સૌથી નજીકના પોઇન્ટ્સ હોય તો તેમને "મેળ ખાતા" કહેવામાં આવે છે. સ્પષ્ટપણે, પોઇન્ટ્સની સૌથી નજીકની જોડી મેળ ખાતી જોડી છે. બિંદુઓને ધ્યાનમાં લો અને, જેમ કે ડાબી બાજુએ છે અને ઉપર વર્ણવેલ કેન્દ્રમાં ફાચરમાં આવેલું છે. જો તે સૌથી નજીકનું બિંદુ હોય, તો તે x-દિશામાં સૌથી નજીકનું બિંદુ (આ ફાચરમાં) હોવું જોઈએ. આમ, x-દિશામાં સૌથી નજીકના બિંદુઓની જોડીનો સમૂહ (આ ફાચરની અંદર) એ સૌથી નજીકના બિંદુઓની જોડીનો સમૂહ છે. સમૂહ P માં દરેક બિંદુ p = (x, y) ને નવા બિંદુ પર નકશો બનાવો, જે રૂપાંતરિત બિંદુઓના સમૂહ P 'ની રચના કરે છે. નોંધ લો કે એક બિંદુ માટે, "મુખ્ય" પાંખમાંના બિંદુઓ આ નવી સંકલન પ્રણાલી કરતાં મોટા અથવા નાના હોય છે અને સંકલન કરે છે. બિંદુઓને x, u અને v કોઓર્ડિનેટ્સ દ્વારા સૉર્ટ કરો અને તેમને ગતિશીલ સૉર્ટ કરેલી સૂચિમાં સંગ્રહિત કરો. અંદરના બિંદુઓ પર 2D શ્રેણીનું વૃક્ષ T બનાવો. પ્રાથમિક વૃક્ષમાં દરેક નોડ ડબલ્યુ માટે, ચાલો T (ડબલ્યુ) એ ડબલ્યુ સાથે સંકળાયેલ ગૌણ વૃક્ષ છે. આ શ્રેણી વૃક્ષનો ઉપયોગ બિંદુ માટે "મુખ્ય" ફાચરમાં બિંદુઓને ઓળખવા માટે કરવામાં આવશે. પ્રાથમિક વૃક્ષમાં દરેક નોડ ડબલ્યુ માટે, અને ટી (ડબલ્યુ) માં દરેક નોડ ઇ માટે, જોડી (ડબલ્યુ, ઇ) = (બી, આર) ની ગણતરી કરો, જ્યાં બી (અથવા આર) ને ઇ ની ડાબી (અથવા જમણી) સબટ્રીમાં મહત્તમ (અથવા લઘુત્તમ) એક્સ-કોઓર્ડિનેટ સાથે બિંદુ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. જોડીમાં બિંદુઓ વચ્ચેના અંતર (મૂળ સંકલન પ્રણાલીમાં માપવામાં આવે છે) દ્વારા નિર્ધારિત પ્રાથમિકતાઓ સાથે, જોડી પર ગતિશીલ અગ્રતા કતાર બનાવો. વિમાનને ફેરવવા માટે ઉપરના પગલાંઓનું પુનરાવર્તન કરો, જેથી ક્રમશઃ ગતિશીલ અગ્રતા કતારો ચાલુ થઈ શકે. પી માં બિંદુઓની સૌથી નજીકની જોડી ઉપરની ત્રણ અગ્રતા કતારોમાંથી મેળવેલા લઘુતમ લઘુતમને અનુરૂપ છે. જાળવણી પ્રમાણપત્ર નિષ્ફળતા પ્રાથમિકતા કતારો અને સૉર્ટ કરેલી સૂચિમાં થઇ શકે છે. પોઇન્ટ્સના ક્રમમાં અદલાબદલી T માં ફેરફારનું કારણ બનશે (જેમાં સમય લાગશે), અને અગ્રતા કતારોમાં નિવેશ/કાટનું કારણ બની શકે છે. નોંધ લો કે ઉપર વ્યાખ્યાયિત કરેલા સમૂહોમાં ફેરફારોની સંખ્યા સતત સંખ્યા હોવી જરૂરી નથી. જો કે, કોઈપણ જોડી કે જે પી અને ક્યૂ બદલવાના ક્રમના પરિણામે મેળ ખાતી શરૂ થાય છે અથવા બંધ થાય છે તેમાં પી અને/અથવા ક્યૂ હોવો આવશ્યક છે, અને તેથી ત્યાં માત્ર મેળ ખાતી જોડીની સતત સંખ્યા છે જેને અગ્રતા કતારોમાં દાખલ કરવી/કાઢી નાખવી આવશ્યક છે. માત્ર આ મેળ ખાતી જોડીઓને અપડેટ કરવી બરાબર છે કારણ કે, વ્યાખ્યા મુજબ, માત્ર મેળ ખાતી જોડી પાસે સૌથી નજીકની જોડી બનવાની તક હોય છે. વિશ્લેષણ આ કે. ડી. એસ. છેઃ પ્રતિભાવશીલઃ ઘટના પર પ્રક્રિયા કરવા માટે સમય લે છે સ્થાનિકઃ કારણ કે દરેક બિંદુ ગતિશીલ ક્રમબદ્ધ સૂચિઓ અને ગતિશીલ અગ્રતા કતારોની સતત સંખ્યામાં હાજર હોય છે, તેથી સ્થાન તે માળખાઓના સ્થાનથી અનુસરે છે સઘનતાઃ સઘનતા ગતિશીલ ક્રમબદ્ધ સૂચિઓ અને ગતિશીલ અગ્રતા કતારોની સઘનતાથી અનુસરે છે કાર્યક્ષમઃ ક્રમબદ્ધ સૂચિમાં દરેક અદલાબદલી ગતિશીલ અગ્રતા કતારોમાં સતત સંખ્યામાં નિવેશ અને કાઢી નાખવાનું કારણ બને છે. ધારો કે બિંદુઓની ગતિ સ્યુડો-બીજગણિત છે, ત્યાં અદલાબદલીની બહુપદી સંખ્યા છે, અને તેથી આ કે. ડી. એસ. દ્વારા ઘટનાઓની બહુપદી સંખ્યા પર પ્રક્રિયા કરવામાં આવે છે, જે તેને કાર્યક્ષમ બનાવે છે. સંદર્ભો ગતિશીલ માહિતી માળખાં ભૌમિતિક માહિતી માળખાં