Kinetic convex hull
કાઇનેટિક કન્વેક્સ હલ ડેટા સ્ટ્રક્ચર એ કાઇનેટિક ડેટા સ્ટ્રક્ચર છે જે સતત ફરતા બિંદુઓના સમૂહના કન્વેક્સ હલને જાળવે છે. તેને ડાયનેમિક કન્વેક્સ હલ ડેટા સ્ટ્રક્ચર્સથી અલગ પાડવું જોઈએ, જે સતત ગતિને બદલે બિંદુઓને દાખલ કરવા અથવા કાઢી નાખવા જેવા અલગ ફેરફારોમાંથી પસાર થતા બિંદુઓને સંભાળે છે. 2D કેસ 2-પરિમાણીય ગતિશીલ બહિર્મુખ પત્થરોની સમસ્યા માટે સૌથી વધુ જાણીતું માહિતી માળખું બાસ્ચ, ગુઇબાસ અને હર્શબર્ગર દ્વારા છે. આ માહિતી માળખું પ્રતિભાવશીલ, કાર્યક્ષમ, સઘન અને સ્થાનિક છે. માહિતી માળખું બિંદુઓના સમૂહના બહિર્મુખ પતવારનું દ્વૈત એ રેખાઓના દ્વૈત સમૂહના ઉપલા અને નીચલા પરબિડીયા છે. તેથી, ફરતી રેખાઓના સમૂહના ઉપલા અને નીચલા આવરણની જાળવણી એ ફરતા બિંદુઓના સમૂહના બહિર્મુખ આવરણની જાળવણીની સમકક્ષ છે. ઉપલા અને નીચલા પરબિડીયાઓની ગણતરી કરવી એ સમાન સમસ્યાઓ છે, તેથી રેખાઓના સમૂહના ઉપલા પરબિડીયાઓની ગણતરી કરવી એ ગતિશીલ બિંદુઓના સમૂહના બહિર્મુખ આવરણની ગણતરી કરવા સમાન છે. સ્થિર રેખાઓના સમૂહના ઉપલા પરબિડીયાની ગણતરી વિભાજન અને વિજય અલ્ગોરિધમનો ઉપયોગ કરીને કરી શકાય છે જે રેખાઓને સમાન કદના બે સમૂહમાં વિભાજિત કરે છે, તેમના ઉપલા પરબિડીયું શોધવા માટે પોતાને બે સમૂહ પર પુનરાવર્તિત રીતે બોલાવે છે, અને પછી બે પરિણામી ઉપલા પરબિડીયુંને ભેળવે છે. મર્જ પગલું ઊભી રેખા સ્વીપનો ઉપયોગ કરીને કરવામાં આવે છે. બિંદુઓના પ્રથમ સમૂહને વાદળી અને બિંદુઓના બીજા સમૂહને લાલ કહો. ઉપલા પરબિડીયાઓને મર્જ કરવા માટેનું પ્રમાણભૂત લાઇન સ્વીપ અલ્ગોરિધમ લાલ અને વાદળી ઉપલા પરબિડીયાઓના તમામ શિરોબિંદુઓને ડાબેથી જમણે ફેરવે છે. સૌથી તાજેતરમાં જોવા મળેલા લાલ અને વાદળી બિંદુઓને લાઇન સ્વીપ તરીકે જાળવવામાં આવે છે. જ્યારે કોઈ બિંદુ આવે છે, ત્યારે અલ્ગોરિધમ તપાસે છે કે વિપરીત રંગના છેલ્લા બિંદુને અનુસરીને બિંદુ સેગમેન્ટની ઉપર અથવા નીચે છે કે કેમ. જો તે ઉપર હોય, તો તે બિંદુ મર્જ કરેલા ઉપલા પરબિડીયુંમાં ઉમેરવામાં આવે છે. જો તે છેલ્લા ઉમેરાયેલા બિંદુ કરતાં અલગ રંગનું હોય, તો લાલ અને વાદળી પરબિડીયાઓ ઓળંગી ગયા છે, તેથી આંતરછેદ બિંદુ પણ મર્જ થયેલા ઉપલા પરબિડીયા સાથે ઉમેરવામાં આવે છે. આ અલ્ગોરિધમથી પરિણામી ધાર અને શિરોબિંદુઓનો ક્રમ માત્ર બિંદુઓના ક્રમ અને રેખા-બિંદુની સરખામણીના પરિણામો પર આધારિત છે. આમ, પરિણામને નીચેના પ્રમાણપત્રો સાથે પ્રમાણિત કરી શકાય છેઃ x-પ્રમાણપત્રો () નો ઉપયોગ લાલ અને વાદળી પરબિડીયાઓના શિરોબિંદુઓના ક્રમને પ્રમાણિત કરવા માટે થાય છે. તેઓ શિરોબિંદુઓના સમૂહ પર ગતિશીલ ક્રમબદ્ધ સૂચિ માટેના પ્રમાણપત્રો છે. દરેક પોઇન્ટમાં 2 રેખાઓ હોય છે, અને પ્રમાણપત્રમાં 2 બિંદુઓ હોય છે, તેથી દરેક પ્રમાણપત્રમાં 4 પંક્તિઓ હોય છે. y-પ્રમાણપત્રો () નો ઉપયોગ એ પ્રમાણિત કરવા માટે થાય છે કે શિરોબિંદુ ધારની ઉપર અથવા નીચે છે. અલ્ગોરિધમ દરમિયાન થતી તમામ સરખામણીઓ માટે પ્રમાણપત્રો દેખાય છે. જ્યાં સુધી આ તમામ પ્રમાણપત્રો ધરાવે છે, ત્યાં સુધી મર્જ પગલાં સમાન રીતે ચલાવવામાં આવશે, તેથી પરિણામી ઉપલા પરબિડીયું સમાન હશે. સ્થિર ઉપલા પરબિડીયું અલ્ગોરિધમને પ્રમાણિત કરવા માટે આ પ્રમાણપત્રોનો ઉપયોગ કરીને ઉપલા પરબિડીયું માટે ગતિશીલ માહિતી માળખું બનાવી શકાય છે. જો કે, આ યોજના સ્થાનિક નથી, કારણ કે એક પંક્તિ ઘણા વાય-પ્રમાણપત્રોમાં સામેલ હોય છે જો તે ઉપર અથવા નીચે રહે તો અન્ય પરબિડીયુંમાંથી ઘણા બિંદુઓ આવે છે. આમ, એસ-પ્રમાણપત્રો () રજૂ કરવા જરૂરી છે જે પ્રમાણિત કરે છે કે રેખાનો ઢોળાવ અન્ય રેખાના ઢોળાવ કરતા મોટો અથવા ઓછો છે. તમામ બિંદુઓ માટે નીચેના પ્રમાણપત્રો હોવા એ મર્જથી પરિણામી ધાર અને શિરોબિંદુઓના ક્રમને પ્રમાણિત કરવા માટે પૂરતા છે, જેમાં રેખા દીઠ માત્ર ઓ (1) પ્રમાણપત્રો છેઃ તેની જમણી બાજુના સૌથી નજીકના શિરોબિંદુને સૂચવે છે. આ પ્રમાણપત્ર એવા તમામ બિંદુઓ માટે સંગ્રહિત કરવામાં આવે છે જે બિંદુ કરતાં અલગ રંગ ધરાવે છે, જે તેમને અનુસરે છે. : અથવા. આ પ્રમાણપત્ર આંતરછેદ કરતા તમામ બિંદુઓ માટે સંગ્રહિત કરવામાં આવે છે. તે હરીફની ધારને સૂચવે છે, અન્ય પરબિડીયુંની ધાર જે ઉપર અથવા નીચે છે. : અથવા. આ પ્રમાણપત્ર આંતરછેદ કરતા તમામ બિંદુઓ માટે સંગ્રહિત કરવામાં આવે છે. :. આ પ્રમાણપત્ર તમામ પોઈન્ટ માટે સંગ્રહિત કરવામાં આવે છે જેના માટે અને. :. આ પ્રમાણપત્ર તમામ પોઈન્ટ માટે સંગ્રહિત કરવામાં આવે છે જેના માટે અને. :. આ પ્રમાણપત્ર તમામ પોઈન્ટ માટે સંગ્રહિત કરવામાં આવે છે જેના માટે અને. :. આ પ્રમાણપત્ર તમામ પોઈન્ટ માટે સંગ્રહિત કરવામાં આવે છે જેના માટે અને. :. આ પ્રમાણપત્ર તમામ પોઈન્ટ માટે સંગ્રહિત કરવામાં આવે છે જેના માટે અને. પ્રથમ પ્રમાણપત્ર, લાલ અને વાદળી પરબિડીયાઓમાં બિંદુઓના એક્સ-ઓર્ડરને પ્રમાણિત કરે છે. બીજા અને ત્રીજા પ્રમાણપત્રો, અને, લાલ અને વાદળી પરબિડીયાઓના આંતરછેદોને પ્રમાણિત કરે છે. બાકીના 5 પ્રમાણપત્રો,,,, અને તેની ઉપરની ધારના ઢોળાવની શ્રેણીમાં ઉપરના પરબિડીયાઓમાં ન હોય તેવી ધાર મૂકો. જો ઢોળાવ ક્રમની શરૂઆતમાં અથવા અંતે હોય, અથવા આને પ્રમાણિત કરો. જો તે ક્રમની મધ્યમાં હોય, અને આને પ્રમાણિત કરે, અને પ્રમાણિત કરે કે બે રેખાઓનું આંતરછેદ બિંદુ કે જે ધારનો ઢોળાવ વચ્ચે છે, તે તેની ઉપર છે. આ એક કે ત્રણ પ્રમાણપત્રો એ સાબિત કરવા માટે પૂરતા છે કે બધી ધાર આ રેખાથી ઉપર છે. અગાઉની યોજનાથી વિપરીત તમામ રેખાઓ માત્ર સતત સંખ્યામાં પ્રમાણપત્રોમાં સામેલ હોય છે. જ્યારે પણ આ પ્રમાણપત્રો નિષ્ફળ જાય છે, ત્યારે મર્જ કરેલા પરબિડીયું અને પ્રમાણપત્રોને ઓ (1) સમયમાં અપડેટ કરી શકાય છે. ઉપરના પરબિડીયાઓના પુનરાવર્તિત વિલિનીકરણને પ્રમાણિત કરવા માટે આ પ્રમાણપત્રોનો ઉપયોગ કરીને બહિર્મુખ પત્થરો માટેનું ગતિશીલ માહિતી માળખું બનાવવામાં આવે છે. જ્યારે પણ પ્રમાણપત્રો નિષ્ફળ જાય છે, ત્યારે તેમનું મર્જ અપડેટ કરવામાં આવે છે, અને જો મર્જથી પરિણામી પરબિડીયું બદલાય છે, તો ફેરફારો મર્જના પરિણામ પર આધારિત તમામ મર્જ દ્વારા પ્રચાર કરવામાં આવે છે. કામગીરી આ માહિતી માળખું પ્રતિભાવશીલ, સ્થાનિક, સઘન અને કાર્યક્ષમ છે. આ ઉપલા પરબિડીયુંને પ્રમાણિત કરવા માટે ઉપયોગમાં લેવાતા મર્જની લઘુગણકીય ઊંડાઈને કારણે છે. પ્રતિક્રિયાશીલઃ જ્યારે પ્રમાણપત્ર નિષ્ફળ જાય છે, ત્યારે તે પ્રમાણિત કરે છે તે મર્જને ઠીક કરવા માટે ઓ (1) લે છે. જો પરિણામી પરબિડીયું બદલાય છે, તો ફેરફારને તમામ મર્જ સુધી પ્રચાર કરવો આવશ્યક છે જે બદલાયેલા મર્જના પરિણામ પર આધાર રાખે છે. આવા ઓ (લોગ એન) વિલિનીકરણ છે, તેથી સુધારાઓ કુલ ઓ (લોગ એન) સમયમાં કરી શકાય છે. સ્થાનિકઃ દરેક પંક્તિ સૌથી વધુ ઓ (લોગ એન) પ્રમાણપત્રોમાં સામેલ છે. આનું કારણ એ છે કે દરેક લીટી દરેક મર્જમાં પ્રમાણપત્રોની સતત સંખ્યામાં સામેલ હોય છે, અને દરેક લીટી ઓ (લોગ એન) માં હોય છે જે કુલ મર્જ કરે છે. કોમ્પેક્ટનેસઃ આ ડેટા સ્ટ્રક્ચરમાં ઉપયોગમાં લેવાતા પ્રમાણપત્રોની મહત્તમ સંખ્યા ઓ (એન લોગ એન) છે. આનું કારણ એ છે કે દરેક મર્જમાં મર્જ થયેલી રેખાઓની સંખ્યા સાથે રેખીય સંખ્યાબંધ પ્રમાણપત્રોનો સમાવેશ થાય છે. એન રેખાઓના ઉપલા પરબિડીયુંને પ્રમાણિત કરવા માટે એન/2 રેખાઓના બે સબસેટના મર્જ ઉપલા પરબિડીયું માટે પ્રમાણપત્રો અને પરબિડીયુંના મર્જ માટે પ્રમાણપત્રો જરૂરી છે. આમ એન રેખાઓના ઉપલા પરબિડીયુંને પ્રમાણિત કરવા માટે જરૂરી પ્રમાણપત્રોની સંખ્યા, સી (એન), પુનરાવર્તન સી (એન) = 2સી (એન/2) + ઓ (એન) ને સી (1) = ઓ (1) સાથે સંતોષે છે. વિભાજન અને વિજય પુનરાવર્તનો માટેના મુખ્ય પ્રમેય અનુસાર, C (n) = O (n log n). કાર્યક્ષમતાઃ બીજગણિત અથવા સ્યુડો-બીજગણિત માર્ગ પર આ અલ્ગોરિધમ દ્વારા પ્રક્રિયા કરાયેલ ઘટનાઓની મહત્તમ સંખ્યા બધા માટે લગભગ દ્વિઘાત છે. રેખીય રીતે ફરતા બિંદુઓના કન્વેક્સ પત્થરો સમય બદલી શકે છે. આમ આ માહિતી માળખું કાર્યક્ષમ છે. ઉચ્ચ પરિમાણો 2 કરતા વધુ પરિમાણોમાં ફરતા બિંદુઓના બહિર્મુખ માળખાને જાળવવા માટે કાર્યક્ષમ ગતિશીલ માહિતી માળખું શોધવું એ એક ખુલ્લી સમસ્યા છે. સંબંધિત સમસ્યાઓ કાઇનેટિક કન્વેક્સ હલનો ઉપયોગ નીચેની સંબંધિત સમસ્યાઓને ઉકેલવા માટે થઈ શકે છેઃ કાઇનેટિક વ્યાસ કાઇનેટિક પહોળાઈ કાઇનેટિક મિનિમમ બોક્સ કાઇનેટિક સૌથી નાનું ઘેરાયેલું ડિસ્ક સંદર્ભો કાઇનેટિક ડેટા સ્ટ્રક્ચર્સ કન્વેક્સ હલ અલ્ગોરિધમ્સ