Union and Split Operations on Dynamic Trapezoidal Maps

Monique Teillaud 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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$.
Type de document :
Rapport
RR-2486, INRIA. 1995
Liste complète des métadonnées

https://hal.inria.fr/inria-00074189
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:42:38
Dernière modification le : samedi 27 janvier 2018 - 01:31:30
Document(s) archivé(s) le : mardi 12 avril 2011 - 15:57:31

Fichiers

Identifiants

  • HAL Id : inria-00074189, version 1

Collections

Citation

Monique Teillaud. Union and Split Operations on Dynamic Trapezoidal Maps. RR-2486, INRIA. 1995. 〈inria-00074189〉

Partager

Métriques

Consultations de la notice

215

Téléchargements de fichiers

114