inria-00074189, version 1
Union and Split Operations on Dynamic Trapezoidal Maps
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$.
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- 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
- http://hal.inria.fr/inria-00074189
- oai:hal.inria.fr:inria-00074189
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mercredi 24 Mai 2006, 14:42:38
- Dernière modification le : Mercredi 31 Mai 2006, 14:24:28







Documents associés

Exporter