Kinetisk bredd

En kinetisk bredddatastruktur är en kinetisk datastruktur som upprätthåller bredden på en uppsättning rörliga punkter. I 2D är bredden på en punktuppsättning det minsta avståndet mellan två parallella linjer som innehåller punktuppsättningen i remsan mellan dem. För det tvådimensionella fallet kan den kinetiska datastrukturen för kinetiskt konvext skrov användas för att konstruera en kinetisk datastruktur för bredden av en punktuppsättning som är responsiv , kompakt och effektiv .

2D-fodral

Betrakta de parallella linjerna som innehåller punkten i remsan mellan dem och som har ett minimalt avstånd från varandra. En av linjerna måste innehålla en kant $ab$ på det konvexa skrovet, och den andra linjen måste gå genom en punkt c på det konvexa skrovet så att (a,c) och (b,c) är antipodalpar . ab och c hänvisas till som ett antipodal kant-vertexpar. 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. Om ett par $ab$ och c är ett antipodalt kant-vertex-par, måste x-intervallet för a och b båda skära x-intervallet för c. Det betyder att den gemensamma slutpunkten för x-intervallen för a och b måste ligga inom x-intervallet för c.

Slutpunkterna för båda uppsättningarna av x-intervall kan bibehållas i en kinetisk sorterad lista . När punkter byter, uppdateras listan över antipoda kantpunktspar på lämpligt sätt. De övre och nedre kuverten kan underhållas med hjälp av standarddatastrukturen för kinetiskt konvext skrov . Minsta avstånd mellan kantpunktspar kan upprätthållas med en kinetisk turnering . Användning 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 de antipodala kant-vertexparen och en kinetisk turnering för att hålla paret med minsta avstånd från varandra, diametern på en rörlig punktuppsättning kan 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 bredden på en punktuppsättning kan ändra $\Omega (n^{2})$ gånger, även om punkterna rör sig linjärt. Denna datastruktur är inte lokal eftersom en punkt kan finnas i många antipodala kant-vertex-par, och därmed förekomma många gånger i den kinetiska turneringen.

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

Högre dimensioner

Att effektivt bibehålla den kinetiska bredden av 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

Vidare läsning

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