Abstrakt. För en uppsättning n punkter i planet, presenterar detta papper enkla kinetiska datastrukturer (KDS) för lösningar på några grundläggande närhetsproblem, nämligen alla närmaste grannar problem, de närmaste par problem, och Euclidean minimum spanning träd (EMST) problem. Papperet introducerar också KDS för underhåll av två välstuderade glesa närhetsgrafer, Yao-grafen och Semi-Yao-grafen. Vi använder sparse graf representationer, Pie Delaunay grafen och Equilateral Delaunay grafen, för att ge nya lösningar på närhetsproblemen. Sedan utformar vi KDS som effektivt upprätthåller dessa glesa grafer på en uppsättning n rörliga punkter, där banan för varje punkt antas vara en polynom funktion av konstant maximal grad s. Vi använder den kinetiska Pie Delaunay graf och den kinetiska Equilateral Delaunay graf för att skapa KDS för underhåll av Yao grafen, Semi-Yao grafen, alla närmaste grannar, det närmaste paret, och EMST. Vår KDS användning O(n) utrymme och O(n log n) förbehandlingstid. Vi tillhandahåller de första KDS för underhåll av Semi-Yao grafen och Yao grafen. Våra KDS-processer O(n 2 β2s+2(n)) (resp. O(n 3 β 2 2s+2 (n) log n)) händelser för att upprätthålla Semi-Yao-grafen (resp. Yao-grafen); varje händelse kan behandlas i tid O(log n) i avkortad betydelse. Här är βs(n) = λs(n)/n en extremt långsamt växande funktion och λs(n) är den maximala längden av Davenport-Schinzel sekvenser av ordning s på n symboler. Vår KDS för underhåll av alla närmaste grannar och de närmaste par processer O(n 2 β 2s+2 (n) log n) händelser. För underhåll av EMST, våra KDS-processer O(n 3 β 2 2s+2 (n) log n) händelser. För alla tre av dessa problem kan varje händelse hanteras i tid O(log n) i amortiserad betydelse. Vårt deterministiska kinetiska tillvägagångssätt för underhåll av alla närmaste grannar förbättras med hjälp av en O(log 2 n) faktor den tidigare randomiserade kinetiska algoritmen av Agarwal, Kaplan och Sharir. Dessutom är vår KDS enklare än deras KDS, eftersom vi minskar problemet till endimensionell områdessökning, i motsats till att använda tvådimensionellt områdessökning som i deras KDS. För underhåll av EMST, vår KDS förbättrar den tidigare KDS av Rahmati och Zarei med en nästan linjär faktor i antalet händelser.
Rahmati m.fl. REF presenterar en kinetisk datastruktur för EMST i det plan som behandlar O(n 3 β 2s+2 (n) log n) händelser i värsta fall, där s är ett mått på komplexiteten i punktbanorna och β s (n) är en extremt långsamt växande funktion.
A Simple, Faster Method for Kinetic Proximity Problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}