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 metadatas

https://hal.inria.fr/inria-00413506
Contributor : Olivier Devillers <>
Submitted on : Friday, September 4, 2009 - 1:11:07 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Long-term archiving on: Tuesday, June 15, 2010 - 9:26:47 PM

File

alg-review.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : inria-00413506, version 1

Collections

Citation

Olivier Devillers, Monique Teillaud, Mariette Yvinec. Dynamic location in an arrangement of line segments in the plane. Algorithms Review, ALCOM EC project, 1992, 2 (3), pp.89-103. ⟨inria-00413506⟩

Share

Metrics

Record views

525

Files downloads

77