s'authentifier
version française rss feed

inria-00072122, version 1

Dynamic Additively Weighted Voronoi Diagrams in 2D

Menelaos I. Karavelas 1, Mariette Yvinec ()

N° RR-4466 (2002)

Résumé : In this paper we present a dynamic algorithm for the construction of the additively weighted Voronoi diagram of a set of weighted points on the plane. The novelty in our approach is that we use the dual of the additively weighted Voronoi diagram to represent it. This permits us to perform both insertions and deletions of sites easily. Given a set of n sites, among which h sites have non-empty Voronoi cell, our algorithm constructs the additively weighted Voronoi diagram of in O(n T(h) + h h) expected time, where T(k) is the time to locate the nearest neighbor of a query site within a set of k sites with non-empty Voronoi cell. Deletions can be performed for all sites whether or not their Voronoi cell is empty. The space requiremen- ts for the presented algorithm is O(n). Our algorithm is simple to implement and experimental results suggest an O(n h) behavior.

  • Domaine : Informatique/Autre
  • Mots-clés : ADDITIVELY WEIGHTED VORONOI DIAGRAM / DELAUNAY GRAPH / DUAL GRAPH / DYNAMIC ALGORITHM
  • Référence interne : RR-4466
 
  • inria-00072122, version 1
  • oai:hal.inria.fr:inria-00072122
  • Contributeur : 
  • Soumis le : Mardi 23 Mai 2006, 19:50:48
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:26
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...