Abstrakt. Problemet med att bibehålla geometriska strukturer för punkter i rörelse har studerats väl under årens lopp. Det stora flertalet teoretiska arbete inom detta område har baserats på antagandet att punktrörelse är kontinuerlig och de framtida rörelserna av punkterna är kända i förväg. I praktiken presenteras dock rörelse normalt steg för steg i diskreta tidssteg och den långsiktiga rörelse av punkter är inte känd och kanske inte ens förutsägbar. Vi anser att problemet med att upprätthålla en datastruktur för lagring av en uppsättning punkter under en sådan inkrementell rörelse. Vi presenterar en enkel online-modell där två agenter samarbetar för att upprätthålla strukturen. Man definierar datastrukturen och tillhandahåller en samling certifikat, som garanterar strukturens korrekthet. Den andra kontrollerar att förslaget med tiden uppfyller dessa intyg och underrättar den förste agenten om eventuella överträdelser. Vi presenterar effektiva online-algoritmer för att underhålla både nät och nätträd för en punkt som genomgår inkrementell rörelse. Vi analyserar våra algoritmers effektivitet genom att begränsa deras konkurrensförhållanden i förhållande till en optimal algoritm. Vårt konkurrensförhållande är en funktion av den dubbla dimensionen av utrymmet och (i fallet med nätträdet) höjden på nätträdet.
De presenterade vidare en enkel online-modell där två agenter namngav observatör och byggare samarbetat för att upprätthålla den inkrementella rörelsen REF.
Maintaining nets and net trees under incremental motion
{'venue': 'In Proc. 20th Annu. Internat. Sympos. Algorithms Comput', 'journal': None, 'mag_field_of_study': ['Computer Science']}