s'authentifier
version française rss feed

inria-00074189, version 1

Union and Split Operations on Dynamic Trapezoidal Maps

Monique Teillaud () 1

N° RR-2486 (1995)

Résumé : We propose here algorithms to perform two new operations on an arrangement of line segments in the plane, represented by a trapezoidal map: the split of the map along a given vertical line $D$, and the union of two trapezoidal maps computed in two vertical slabs of the plane that are adjacent through a vertical line $D$. The data structure is a modified Influence graph, still allowing dynamic insertions and deletions of line segments in themap. The algorithms for both operations run in $O(s_D \log n +\log^2 n)$ time, where $n$ is the number of line segments in the map, and $s_D$ is the number of line segments intersected by $D$.

  • Domaine : Informatique/Autre
  • Mots-clés : COMPUTATIONAL GEOMETRY / DYNAMIC ALGORITHMS / RANDOMIZED ALGORITHMS / DATA STRUCTURES / TRAPEZOIDAL MAP
  • Référence interne : RR-2486
 
  • inria-00074189, version 1
  • oai:hal.inria.fr:inria-00074189
  • Contributeur : 
  • Soumis le : Mercredi 24 Mai 2006, 14:42:38
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:28
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...