Skip to Main content Skip to Navigation

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$.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 2:42:38 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 3:57:31 PM


  • HAL Id : inria-00074189, version 1



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



Record views


Files downloads