Kinetisk närmaste par

En kinetisk närmaste par datastruktur är en kinetisk datastruktur som upprätthåller det närmaste paret av punkter , givet en uppsättning P av n punkter som rör sig kontinuerligt med tiden i ett metriskt utrymme. Även om många effektiva algoritmer var kända i det statiska fallet, visade de sig vara svåra att kinetisera , så nya statiska algoritmer utvecklades för att lösa detta problem.

2D-fodral

Tillvägagångssätt 1

Det enklaste kinetiska tillvägagångssättet för underhåll av det närmaste paret är att använda varianter av Delaunay-trianguleringarna .

Betrakta en hexagon och dela upp den i sex liksidiga trianglar och skapa sedan en Delaunay-triangulering baserat på varje liksidig triangel, eftersom var och en har en konvex form. Föreningen av dessa sex Delaunay-trianguleringar, så kallad Equilateral Delaunay-graf (EDG), är en supergraf för den närmaste granngrafen (NNG); ändpunkterna på kanten med minsta längd i EDG ger det närmaste paret. Det är enkelt att underhålla Delaunay-trianguleringar baserade på konvexa former. Med tanke på EDG över tid, genom att skapa ett kinetiskt turneringsträd över kanterna på EDG, kan man enkelt behålla det närmaste paret.

Det här närmaste paret KDS är effektivt, avskrivningskänsligt och kompakt, men är i allmänhet inte lokalt. Följande tillvägagångssätt presenterar en lokal KDS för underhåll av det närmaste paret.

Tillvägagångssätt 2

Det andra kinetiska tillvägagångssättet är baserat på följande observationer.

Söndra och erövra

Om utrymmet runt en punkt p är indelat i vinkel i sex "kilar", var och en 60° bred, är den närmaste punkten p den närmaste av de närmaste punkterna i var och en av kilarna. Resten av den här artikeln kommer att fokusera på de "huvudsakliga" kilarna (de som delas av x-axeln), och symmetriska argument kommer att gälla för de andra kilarna efter att ha roterat planet med ±60 ° .

Matchade poäng

Punkterna p och q sägs vara "matchade" om de ligger närmast varandra. Det är uppenbart att det närmaste poängparet är ett matchat par.

Betrakta punkterna p och q , så att p är till vänster om q och q ligger i kilen centrerad vid p som beskrivs ovan. Om p är den punkt som ligger närmast q måste q vara den punkt som ligger närmast (i den här kilen) p , i x-riktningen. Således är uppsättningen av par av närmaste punkter (inom denna kil) i x-riktningen en supermängd av uppsättningen av par av närmaste punkter.

Konstruktion

1. Kartlägg varje punkt p =( x , y ) i mängden P till en ny punkt p' = ( u , v ) = ( x + √ 3 y , y - √ 3 x ) , och bildar mängden P' av transformerade punkter. Observera att för en punkt p har punkterna i "huvud"-kilarna u- och v -koordinater antingen större eller mindre än p' i detta nya koordinatsystem.
2. Sortera punkterna efter x , u och v koordinater och lagra dem i kinetiskt sorterade listor .
3. Konstruera ett 2D- avståndsträd T på punkterna i P' . För varje nod w i det primära trädet, låt T ( w ) vara det sekundära trädet associerat med w . Detta områdesträd kommer att användas för att identifiera punkterna i "huvudkilen" för en punkt w .
4. För varje nod w i det primära trädet, och varje nod e i T ( w ), beräkna paret π ( w , e ) = ( b , r ), där b (eller r ) definieras som punkten med maximum ( eller minimum) x-koordinat i det vänstra (eller högra) underträdet av e . Låt Π(0) vara mängden π ( w , e ) för alla par w , e i T . Detta är en superset av uppsättningen par av närmaste punkter (inom huvudkilen).
5. Bygg en kinetisk prioritetskö på paren i Π(0) , med prioriteringar som bestäms av avståndet (mätt i det ursprungliga koordinatsystemet) mellan punkterna i paret.
6. Upprepa stegen ovan för planet roterat ±60° för att få kinetiska prioritetsköer på Π(1) respektive Π(-1) .

Det närmaste paret av punkter i P motsvarar det minimum av minimumen som erhålls från de tre prioritetsköerna Π ovan.

Underhåll

Certifikatfel kan uppstå i prioritetsköerna och de sorterade listorna. Byten i ordningen av punkterna kommer att orsaka ändringar av T (vilket tar O (log ² n ) tid), och kan orsaka insättningar/borttagningar i prioritetsköerna.

Observera att antalet ändringar av mängderna Π enligt definitionen ovan inte behöver vara ett konstant antal. Alla par som startar eller slutar att matchas som ett resultat av ordningen av p och q ändring måste dock innehålla p och/eller q, och därför finns det bara ett konstant antal matchade par som måste infogas i/raderas från prioriteten köer. Det är ok att bara uppdatera dessa matchade par eftersom, per definition, endast matchade par har en chans att vara det närmaste paret.

Analys

Denna KDS är:

• Responsiv : tar O (log ² n ) tid att bearbeta en händelse
• Lokal : eftersom varje punkt finns i ett konstant antal kinetiskt sorterade listor och kinetiska prioritetsköer, följer lokalitet från lokaliteten för dessa strukturer
• Kompakthet : kompakthet följer av kompaktheten hos de kinetiskt sorterade listorna och kinetiska prioritetsköerna
• Effektivt : varje växling i de sorterade listorna orsakar ett konstant antal infogningar och borttagningar i de kinetiska prioritetsköerna. Om man antar att punkternas rörelse är pseudo-algebraisk, finns det ett polynomantal byten, och följaktligen behandlas ett polynomantal händelser av denna KDS, vilket gör den effektiv

Detta tillvägagångssätt kan användas för att bibehålla det närmaste paret i högre dimensioner.