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.
Type de document :
Article dans une revue
Algorithms Review, ALCOM EC project, 1992, 2 (3), pp.89-103
Liste complète des métadonnées

Contributeur : Olivier Devillers <>
Soumis le : vendredi 4 septembre 2009 - 13:11:07
Dernière modification le : mardi 24 avril 2018 - 17:20:10
Document(s) archivé(s) le : mardi 15 juin 2010 - 21:26:47


Fichiers éditeurs autorisés sur une archive ouverte


  • 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, ALCOM EC project, 1992, 2 (3), pp.89-103. 〈inria-00413506〉



Consultations de la notice


Téléchargements de fichiers