Abstrakt. I detta papper presenterar vi en dynamisk algoritm för konstruktion av additivt viktade Voronoi diagram av en uppsättning viktade punkter i planet. Nytt i vår strategi är att vi använder den dubbla av additivt viktade Voronoi diagram för att representera det. Detta gör det möjligt för oss att utföra både tillägg och raderingar av webbplatser enkelt. Med tanke på en uppsättning B av n platser, bland vilka h platser har en icke-tom cell, vår algoritm konstruerar additivt viktade Voronoi diagram av B i O(nT (h) + h log h) förväntad tid, där T (k) är tiden att lokalisera närmaste granne till en frågeplats inom en uppsättning k platser. Deleations kan utföras för alla platser oavsett om deras cell är tom eller inte. Utrymmeskraven för den presenterade algoritmen är O(n). Vår algoritm är enkel att implementera och experimentella resultat tyder på ett O(n log h) beteende.
Karavelas och Yvinec REF tillhandahöll en O(nT (h) + h log h) tid algoritm för att beräkna AW-Voronoi diagram där h är antalet icke-tomma celler och T (h) är tiden att lokalisera närmaste granne av en frågepunkt inom en uppsättning av h punkter.
Dynamic additively weighted Voronoi diagrams in 2 D ?
{'venue': 'International Conference on Computational Science (1)', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}