HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:42:38 PM
Last modification on : Friday, February 4, 2022 - 3:16:07 AM
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