Kinetiskt konvext skrov

En kinetisk konvex skrovdatastruktur är en kinetisk datastruktur som upprätthåller det konvexa skrovet för en uppsättning kontinuerligt rörliga punkter. Det bör särskiljas från dynamiska konvexa skrovdatastrukturer, som hanterar punkter som genomgår diskreta förändringar såsom infogning eller radering av punkter snarare än kontinuerlig rörelse.

2D-fallet

Den mest kända datastrukturen för det 2-dimensionella kinetiska konvexa skrovproblemet är av Basch, Guibas och Hershberger. Denna datastruktur är lyhörd , effektiv , kompakt och lokal .

Datastrukturen

Den dubbla av ett konvext skrov av en uppsättning punkter är de övre och nedre kuverten av den dubbla uppsättningen av linjer. Att bibehålla de övre och nedre höljena av en uppsättning rörliga linjer är därför ekvivalent med att bibehålla det konvexa skrovet för en uppsättning rörliga punkter. Att beräkna övre och nedre kuvert är likvärdiga problem, så att beräkna det övre kuvertet för en uppsättning linjer är likvärdigt med att beräkna det konvexa skrovet för en uppsättning rörliga punkter. Den övre enveloppen av en uppsättning statiska linjer kan beräknas med hjälp av en divide and conquer-algoritm som delar upp raderna i två uppsättningar av samma storlek, anropar sig själv rekursivt på de två uppsättningarna för att hitta deras övre kuvert och sedan slår samman de två resulterande övre kuverten. . Sammanfogningssteget utförs med en vertikal linjesvepning . Kalla den första uppsättningen punkter blå och den andra uppsättningen punkter röd.

Standardlinjesvepalgoritmen för att slå samman övre kuvert sveper genom alla hörn av de röda och blå övre kuverten, från vänster till höger. De senast påträffade röda och blå punkterna bibehålls när linjen sveper. När en punkt påträffas kontrollerar algoritmen om punkten är över eller under segmentet efter den senast påträffade punkten i motsatt färg. Om den är ovan läggs den punkten till det sammanslagna övre kuvertet. Om den har en annan färg än den senast tillagda punkten har de röda och blå kuverten korsats, så skärningspunkten läggs också till det sammanslagna övre kuvertet.

Sekvensen av kanter och hörn som resulterar från denna algoritm är endast beroende av ordningen av punkter och resultaten av linjepunktsjämförelserna. Således kan resultatet certifieras med följande certifikat:

x-certifikat ( $<_{x}$ ) används för att certifiera ordningen på hörnen på de röda och blå kuverten. De är certifikaten för en kinetisk sorterad lista på uppsättningen av hörn. Eftersom varje punkt omfattar 2 rader och certifikatet innebär 2 poäng, innebär varje certifikat 4 rader.
y-certifikat ( $<_{y}$ ) används för att intyga att en vertex är över eller under en kant. Certifikaten visas för alla jämförelser som skulle inträffa under algoritmen.

Så länge som alla dessa certifikat håller, kommer sammanslagningsstegen att utföras identiskt, så det resulterande övre kuvertet blir detsamma. En kinetisk datastruktur för övre envelopp kan skapas genom att använda dessa certifikat för att certifiera den statiska övre envelope-algoritmen. Detta schema är dock inte lokalt, eftersom en rad många är inblandade i många y-certifikat om den förblir på toppen eller botten så många punkter från det andra kuvertet påträffas.

Det är alltså nödvändigt att införa ett s-certifikat ( $<_{s}$ ) som intygar att lutningen på en linje är större än eller mindre än lutningen på en annan linje.

Att ha följande certifikat för alla punkter ab är tillräckligt för att certifiera sekvensen av kanter och hörn som är resultatet av en sammanslagning, med endast O(1)-certifikat per rad:

A picture of the certificates in several difference cases

Certifikaten intygar strukturen för skärningspunkten mellan de röda och blå kuverten genom att intyga korsningar (överst till vänster) eller frånvaron av korsningar (överst till höger och längst ner). Pilarna indikerar vilka element som jämförs av certifikatet.

$x[ab]$ : $ab<_{x}ab.next$ . $ab.next$ anger spetsen närmast $ab$ till höger. Detta certifikat lagras för alla punkter $ab$ som har en annan färg än punkten, $ab.next$ , som följer dem.
$yli[ab]$ : $ab<_{y}ce(ab)$ eller $ab>_{y}ce(ab)$ . Detta certifikat lagras för alla punkter $ab$ så att $b$ skär $ce(ab)$ . $ce(ab)$ betecknar utmanarkanten på $ab$ , kanten från det andra kuvertet som är över eller under $ab$ .
$yri[ab]$ : $ab<_{y}ce(ab)$ eller $ab>_{y}ce(ab)$ . Detta certifikat lagras för alla punkter $ab$ så att $a$ skär $ce(ab)$ .
$yt[ab]$ : $ce(ab)<_{y}ab$ . Detta certifikat lagras för alla punkter $ab$ för vilka $a<_{s}ce(ab)<_{s}b$ och $ce(ab)<_{y}ab$ .
$srt[ab]$ : $a<_{s}ce(ab)$ . Detta certifikat lagras för alla punkter $ab$ för vilka $a<_{s}ce(ab)<_{s}b$ och $ce(ab)<_{y}ab$ .
$srt[ab]$ : $ce(ab)<_{s}b$ . Detta certifikat lagras för alla punkter $ab$ för vilka $a<_{s}ce(ab)<_{s}b$ och $ce(ab)<_{y}ab$ .
$sl[ab]$ : $b<_{s}ce(ab)$ . Detta certifikat lagras för alla punkter $ab$ för vilka $b<_{s}ce(ab)$ och $ab<_{y}ce(ab)$ .
$sr[ab]$ : $ce(ab)<_{s}a$ . Detta certifikat lagras för alla punkter $ab$ för vilka $ce(ab)<_{s}a$ och $ab<_{y}ce(ab)$ .

Det första certifikatet, $x[ab]$ , intygar x-ordningen av punkterna i de röda och blå kuverten. Det andra och tredje certifikatet, $yli[ab]$ och $yri[ab]$ , intygar skärningspunkterna mellan de röda och blå kuverten. De återstående 5 certifikaten, $yt[ab]$ , $srt[ab]$ , $srt[ab]$ , $sl[ab]$ och $sr[ab]$ placerar kanter som inte finns i de övre kuverten i sekvensen av lutningar av kanterna som är över det. Om lutningen är i början eller slutet av sekvensen, intygar $sl$ eller ${\displaystyle sr} detta.$ Om det är mitt i sekvensen $slt$ , och $srt$ intygar detta, och $yt$ intygar att skärningspunkten för de två linjerna som kantens lutning är mellan, är ovanför den. Dessa ett eller tre certifikat räcker för att bevisa att alla kanter är ovanför denna linje. Till skillnad från det tidigare schemat är alla linjer endast involverade i ett konstant antal certifikat. Närhelst av dessa certifikat misslyckas kan det sammanslagna kuvertet och certifikaten uppdateras i O(1) tid.

Den kinetiska datastrukturen för konvext skrov är konstruerad genom att använda dessa certifikat för att certifiera den rekursiva sammansmältningen av de övre kuverten. Närhelst certifikat misslyckas uppdateras deras sammanslagning, och om kuvertet som blir resultatet av sammanslagningen ändras sprids ändringarna upp genom alla sammanslagningar som beror på resultatet av sammanslagningen.

Prestanda

Denna datastruktur är lyhörd , lokal , kompakt och effektiv . Detta beror på det logaritmiska djupet av sammanslagningarna som används för att certifiera det övre kuvertet.

Responsiv: När ett certifikat misslyckas krävs O(1) för att fixa sammanslagningen som det certifierar. Om det resulterande kuvertet ändras måste ändringen spridas upp till alla sammanslagningar som beror på resultatet av den ändrade sammanslagningen. Det finns O(log n ) sådana sammanslagningar, så uppdateringen kan utföras i O(log n ) total tid.
Lokalt: Varje rad är involverad i ett mest O(log n ) certifikat. Detta beror på att varje rad är involverad i ett konstant antal certifikat i varje sammanslagning, och varje rad är i O(log n ) sammanslagningar totalt.
Kompakthet: Det maximala antalet certifikat som används i denna datastruktur är O( n log n ). Detta beror på att varje sammanslagning involverar ett antal certifikat som är linjärt i förhållande till antalet sammanslagna rader. För att certifiera ett övre kuvert med n rader krävs certifikat för sammanslagningen av övre kuvert av de två delmängderna av n /2 rader, och certifikat för sammanslagning av kuverten. Således uppfyller antalet certifikat, C( n ), som krävs för att certifiera det övre kuvertet av n rader återkommande C( n )=2C( n /2)+O( n ), med C(1)=O(1) . Enligt mastersatsen för dela-och-härska-recidiv , C( n )=O( n log n ).
Effektivitet: Det maximala antalet händelser som behandlas av denna algoritm på algebraiska eller pseudo-algebraiska banor är nära kvadratiskt, $O(n^{2+\epsilon })$ för alla ${\ displaystyle \epsilon >0}$ . Konvexa skrov med linjärt rörliga punkter kan ändra $\Omega (n^{2})$ gånger. Således är denna datastruktur effektiv.

Högre dimensioner

Att hitta en effektiv kinetisk datastruktur för att bibehålla det konvexa skrovet av rörliga punkter i dimensioner högre än 2 är ett öppet problem.

Relaterade problem

Kinetiskt konvext skrov kan användas för att lösa följande relaterade problem: