Skip to Main content Skip to Navigation
New interface
Journal articles

Dynamic location in an arrangement of line segments in the plane

Abstract : We describe in this paper an algorithm which dynamically maintains the trapezoidal map of an arrangement of line segments. This algorithm is a generalization of the Influence Graph data structure used by Boissonnat et al. to deal with the semi-dynamic case. Our complexity results are randomized, i.e. the insertion sequences are supposed to be evenly distributed among the n! possible sequences of $ segments, and when an object is deleted, we suppose that it can be any of the already inserted objects with the same probability. Under these assumptions the algorithm needs O(n+a) expected space, O(log n + a/n) expected insertion time, O( (1+ a/n)loglog n) expected deletion time and O(log n) time to locate any query point in the arrangement, where a is the current size of the arrangement and n the current number of segments.
Document type :
Journal articles
Complete list of metadata
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, September 4, 2009 - 1:11:07 PM
Last modification on : Thursday, March 17, 2022 - 10:08:24 AM
Long-term archiving on: : Tuesday, June 15, 2010 - 9:26:47 PM


Publisher files allowed on an open archive


  • HAL Id : inria-00413506, version 1



Olivier Devillers, Monique Teillaud, Mariette Yvinec. Dynamic location in an arrangement of line segments in the plane. Algorithms Review - newsletter of the ESPRIT II Basic Research Action Project no. 3075 (ALCOM) , 1992, 2 (3), pp.89-103. ⟨inria-00413506⟩



Record views


Files downloads