Kinetisk sorterad lista

En kinetisk sorterad lista är en kinetisk datastruktur för att upprätthålla en lista över punkter under rörelse i sorterad ordning. Det används som en kinetisk föregångare datastruktur och som en komponent i mer komplexa kinetiska datastrukturer som kinetic closest pair .

Genomförande

Denna datastruktur upprätthåller en lista över elementen i sorterad ordning, med certifikaten som upprätthåller ordningen mellan intilliggande element. När ett certifikat misslyckas byts de berörda elementen. Då måste högst tre certifikat uppdateras, certifikatet för det utbytta paret, och de två certifikaten som involverar de utbytta elementen och de element i den sorterade listan som direkt föregår och följer efter det utbytta paret.

Till exempel, givet en sorterad lista {A,B,C,D,E,F} kommer certifikaten att vara [A

Analys

Denna kinetiska datastruktur är:

• Responsive : ett certifikatfel orsakar ett byte (vilket tar O(1) tid) och O(1) certifikatändringar som tar O(log n) tid att schemalägga
• Lokalt : varje element är involverat i högst 2 certifikat
• Kompakt : det finns exakt n -1 certifikat för en lista med n element
• Effektiv : denna datastruktur orsakar inga främmande interna händelser , varje förändring i ordningen av elementen orsakar exakt ett certifikatfel.

Generalisering

Denna datastruktur kan generaliseras till en kinetisk datastruktur som kan returnera en sorterad lista med punkter i $O(n\log m)$ tid och processer $O({\frac {n^{2}}{m}})$ händelser totalt, med antagande av pseudoalgebraiska banor, där $m$ är en parameter i datastrukturen. Således kan en avvägning mellan underhållstid och frågetid göras för att anpassas till specifika applikationer.

I den generaliserade datastrukturen är punkterna uppdelade godtyckligt i m delmängder med storleken ${\displaystyle O({\frac {n}{m}})} och kinetiskt$ listor upprätthålls på delmängderna. Varje sorterad underlista behöver maximalt bearbeta $O({\frac {n^{2}}{m^{2}}})$ händelser (certifikatfel), eftersom det finns $O(1)$ byten av vart och ett av $O({\frac {n^{2}}{m^{2}}})$ elementpar . Den totala tiden som krävs för att upprätthålla datastrukturen är $O({\frac {n^{2}}{m}})$ . Förfrågningar om den sorterade listan kan sedan besvaras i $O(n\log m)$ genom att slå samman de sorterade underlistorna med mergesort .

• Abam, MA; De Berg, M. (2007), "Kinetic sorting and kinetic convex hulls", Special Issue on the Twenty-First Annual Symposium on Computational Geometry — SoCG 2005, Computational Geometry: Theory and Applications , 37 (1): 16–26, doi : 10.1016/j.comgeo.2006.02.004 .