Dynamiskt konvext skrov

Det dynamiska konvexa skrovproblemet är en klass av dynamiska problem inom beräkningsgeometri . Problemet består i underhållet, dvs att hålla reda på, det konvexa skrovet för indata som genomgår en sekvens av diskreta förändringar, dvs när indataelement kan infogas, raderas eller modifieras. Det bör särskiljas från det kinetiska konvexa skrovet , som studerar liknande problem för kontinuerligt rörliga punkter. Dynamiska konvexa skrovproblem kan särskiljas av typen av indata och de tillåtna typerna av modifiering av indata.

Plan punktuppsättning

Det är lätt att konstruera ett exempel där det konvexa skrovet innehåller alla ingångspunkter, men efter införandet av en enda punkt blir det konvexa skrovet en triangel. Och omvänt kan raderingen av en enda punkt ge den motsatta drastiska förändringen av storleken på utdata. Därför, om det konvexa skrovet måste rapporteras på traditionellt sätt som en polygon, är den nedre gränsen för den värsta beräkningskomplexiteten för omräkningen av det konvexa skrovet $\Omega (N)$ , eftersom denna tid krävs för en ren rapportering av resultatet. Denna nedre gräns kan uppnås, eftersom flera allmänna konvexa skrovalgoritmer körs i linjär tid när ingångspunkter är ordnade på något sätt och logaritmiska tidsmetoder för dynamiskt underhåll av ordnade data är välkända.

Detta problem kan övervinnas genom att eliminera begränsningen av utmatningsrepresentationen. Det finns datastrukturer som kan upprätthålla representationer av det konvexa skrovet under en tid per uppdatering som är mycket mindre än linjär. Under många år var den bästa algoritmen av denna typ den av Overmars och van Leeuwen (1981), som tog tid O(log ² n ) per uppdatering, men den har sedan dess förbättrats av Timothy M. Chan och andra.

I ett antal tillämpningar är att hitta det konvexa skrovet ett steg i en algoritm för att lösa det övergripande problemet. Den valda representationen av det konvexa skrovet kan påverka beräkningskomplexiteten för ytterligare operationer av den övergripande algoritmen. Till exempel punkten i polygonfrågan för en konvex polygon som representeras av den ordnade uppsättningen av dess hörn besvaras i logaritmisk tid, vilket skulle vara omöjligt för konvexa skrov som rapporteras av uppsättningen av dess hörn utan ytterligare information. Därför involverar viss forskning av dynamiska konvexa skrovalgoritmer beräkningskomplexiteten hos olika geometriska sökproblem med konvexa skrov lagrade i specifika typer av datastrukturer. Det nämnda tillvägagångssättet hos Overmars och van Leeuwen möjliggör logaritmisk komplexitet för olika vanliga frågor.

Alexandron, Giora; Kaplan, Haim; Sharir, Micha (2005), "Kinetiska och dynamiska datastrukturer för konvexa skrov och övre envelopes", Algorithms and Data Structures (WADS 2005), Lecture Notes in Computer Science, vol. 3608, Berlin: Springer, s. 269–281, doi : 10.1007/11534273_24 , MR 2200329
Brodal, Gerth Stølting; Jacob, Riko (2000), "Dynamiskt plan konvext skrov med optimal frågetid och $O(\log n\cdot \log \log n)$ uppdateringstid", Algorithm Theory (SWAT 2000, Bergen) , Lecture Notes in Computer Science, vol. 1851, Berlin: Springer, s. 57–70, doi : 10.1007/3-540-44985-X_7 , MR 1792585
Chan, Timothy M. (2001), "Dynamic planar convex hull operations in near-logarithmic amortized time", Journal of the ACM , 48 (1): 1–12, doi : 10.1145/363647.363652 , MR 1867273
Chan, Timothy M. (2010), "A dynamic data structure for 3-D convex hulls and 2-D nearest neighbour queries", Journal of the ACM , 57 (3): A16:1–A16:15, doi : 10.1145 /1706591.1706596 , MR 2665885
Chan, Timothy M. (2012), "Three problems about dynamic convex hulls", International Journal of Computational Geometry & Applications , 22 (4): 341–364, doi : 10.1142/S0218195912600096 , MR 8 29945
Demaine, Erik D. ; Pǎtraşcu, Mihai (2007), "Snäva gränser för dynamiska konvexa skrovfrågor (igen)", Proc. Symp. Computational Geometry (SoCG 2007) , New York: ACM, s. 354–363, doi : 10.1145/1247069.1247131 , MR 2469185
Hershberger, John ; Suri, Subhash (1992), "Applications of a semi-dynamic convex hull algorithm", BIT , 32 (2): 249–267, doi : 10.1007/BF01994880 , MR 1172189
Åh, Eunjin; Ahn, Hee-Kap (2017), "Dynamic geodesic convex hulls in dynamic simple polygons", 33rd International Symposium on Computational Geometry (SoCG 2017) , LIPIcs, vol. 77, Schloss Dagstuhl, s. 51:1–51:15, doi : 10.4230/LIPIcs.SoCG.2017.51 , MR 3685723
Overmars, MH ; van Leeuwen, J. (1981), "Maintenance of configurations in the plane", Journal of Computer and System Sciences , 23 (2): 166–204, doi : 10.1016/0022-0000(81)90012-X .