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
Reports

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 :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074189
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

Identifiers

  • HAL Id : inria-00074189, version 1

Collections

Citation

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

Share

Metrics

Record views

96

Files downloads

134