s'authentifier
version française rss feed

inria-00071561, version 1

The Voronoi Diagram of Convex Objects in the Plane

Menelaos Karavelas a, Mariette Yvinec () 1

N° RR-5023 (2003)

Résumé : This paper presents a dynamic algorithm for the construction of the Euclidean Voronoi diagram of a set of convex objects in the plane. We consider first the Voronoi diagram of smooth convex objects forming pseudo-circles set. A pseudo-circles set is a set of bounded objects such that the boundaries of any two objects intersect at most twice. Our algorithm is a randomized dynamic algorithm. It does not use a conflict graph or any sophisticated data structure to perform conflict detection. This feature allows us to handle deletions in a relatively easy way. In the case where objects do not intersect, the randomized complexity of an insertion or deletion can be shown to be respectively O(^2 n) and O(^3 n). Our algorithm can easily be adapted to the case of pseudo-circles sets formed by piecewise smooth convex objects. Finally, given any set of convex objects in the plane, we show how to compute the restriction of the Voronoi diagram in the complement of the objects' union.

  • Domaine : Informatique/Autre
  • Mots-clés : VORONO DIAGRAM – DELAUNAY TRIANGULATION – EUCLIDEAN DISTANCE – ABSTRACT VORONOI DIAGRAM – RANDOMIZED ALGORITHM – DYNAMIC ALGORITHMS
  • Référence interne : RR-5023
 
  • inria-00071561, version 1
  • oai:hal.inria.fr:inria-00071561
  • Contributeur : 
  • Soumis le : Mardi 23 Mai 2006, 17:57:17
  • Dernière modification le : Vendredi 26 Janvier 2007, 11:01:04
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...