Kinetisk diameter (data)

En kinetisk diameterdatastruktur är en kinetisk datastruktur som upprätthåller diametern för en uppsättning rörliga punkter. Diametern på en uppsättning rörliga punkter är det maximala avståndet mellan något par av punkter i uppsättningen. I det tvådimensionella fallet kan den kinetiska datastrukturen för kinetiskt konvext skrov användas för att konstruera en kinetisk datastruktur för diametern på en rörlig punktuppsättning som är lyhörd , kompakt och effektiv .

2D-fodral

Punktparet med maximalt parvis avstånd måste vara ett av paren av antipodalpunkter i det konvexa skrovet av alla punkter. Observera att två punkter är antipodalpunkter om de har parallella stödlinjer . I det statiska fallet kan en punktuppsättnings diameter hittas genom att beräkna punktuppsättningens konvexa skrov, hitta alla par av antipodalpunkter och sedan hitta det maximala avståndet mellan dessa par. Denna algoritm kan kinetiseras enligt följande:

Betrakta dual av punktuppsättningen. Punkterna dualiseras till linjer och det konvexa skrovet på punkterna dualiseras till det övre och nedre höljet av linjeuppsättningen . Topparna på det övre konvexa skrovet dualiseras till segment på det övre höljet. Topparna på det nedre konvexa skrovet dualiseras till segment på det nedre höljet. Omfånget av lutningar för stödlinjerna för en punkt på skrovet dualiseras till x-intervallet för segmentet som punkten dualiserar till. När de ses på detta dualiserade sätt är antipodalparen par av segment, ett från det övre höljet, ett från det nedre, med överlappande x-områden. Nu kan de övre och nedre kuverten ses som två olika x-ordnade listor med icke överlappande intervall. Om dessa två listor slås samman är antipodalparen överlappningarna i den sammanslagna listan.

Överlappningarna i den sammanslagna listan med x-intervall kan upprätthållas genom att lagra ändpunkterna för intervallen i en kinetisk sorterad lista . När poäng byter uppdateras listan över antipodalpar. De övre och nedre kuverten kan underhållas med hjälp av standarddatastrukturen för kinetiskt konvext skrov . Det maximala avståndet mellan par av antipodal kan upprätthållas med en kinetisk turnering . Med hjälp av kinetiskt konvext skrov för att bibehålla de övre och nedre kuverten, en kinetisk sorterad lista på dessa intervall för att bibehålla antipodalparen och en kinetisk turnering för att hålla paret på maximalt avstånd från varandra, kan diametern på en rörlig punktuppsättning bibehållas .

Denna datastruktur är lyhörd , kompakt och effektiv . Datastrukturen använder $O(n)$ utrymme eftersom det kinetiska konvexa skrovet, sorterade listan och turneringsdatastrukturerna alla använder $O(n)$ utrymme. I alla datastrukturer kan händelser, infogningar och borttagningar hanteras i $O(\log ^{2}n)$ tid, så datastrukturen är responsiv och kräver $O(\log ^{2}n)$ per händelse. Datastrukturen är effektiv eftersom det totala antalet händelser är $O(n^{2+\epsilon })$ för alla $\epsilon >0$ och diametern på en punktuppsättning kan ändra $\Omega (n^{2})$ gånger, även om punkterna rör sig linjärt. Den här datastrukturen är inte lokal eftersom en punkt kan finnas i många antipodalpar, och därmed förekomma många gånger i den kinetiska turneringen.

Förekomsten av en lokal kinetisk datastruktur för diameter är öppen.

Högre dimensioner

Att effektivt bibehålla den kinetiska diametern för en punktuppsättning i dimensioner högre än 2 är ett öppet problem. Effektivt kinetiskt konvext skrov i dimensioner högre än 2 är också ett öppet problem.

Relaterade problem

PK Agarwal, LJ Guibas, J. Hershberger och E. Verach. Upprätthålla omfattningen av en rörlig uppsättning punkter.