O. [. Aurenhammer, . [. Schwarzkopf, K. Boissonnat, and . Dobrindt, A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMS, Proc. 4th Canad. Conf. Comput. Geom, pp.363-381, 1992.
DOI : 10.1142/S0218195992000214

[. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete & Computational Geometry, vol.20, issue.1, pp.51-71, 1992.
DOI : 10.1007/BF02293035
URL : https://hal.archives-ouvertes.fr/inria-00075274

[. Boissonnat, O. Devillers, and M. Teillaud, A semidynamic construction of higher-order voronoi diagrams and its randomized analysis, Algorithmica, vol.8, issue.4, pp.329-356, 1993.
DOI : 10.1007/BF01228508
URL : https://hal.archives-ouvertes.fr/inria-00090668

J. Boissonnat and M. Teillaud, The hierarchical representation of objects: the Delaunay tree, Proceedings of the second annual symposium on Computational geometry , SCG '86, pp.260-268, 1986.
DOI : 10.1145/10515.10543

[. Boissonnat and M. Teillaud, On the randomized construction of the Delaunay tree, Theoretical Computer Science, vol.112, issue.2, pp.339-354, 1993.
DOI : 10.1016/0304-3975(93)90024-N
URL : https://hal.archives-ouvertes.fr/inria-00075419

H. [. Chazelle and . Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM, vol.39, issue.1, pp.1-54, 1992.
DOI : 10.1145/147508.147511

. Ceg-+-93-]-b, H. Chazelle, L. Edelsbrunner, M. Guibas, J. Sharir et al., Computing a face in an arrangement of line segments, SIAM J. Comput, vol.22, pp.1286-1302, 1993.

]. K. Cla87 and . Clarkson, New applications of random sampling in computational geometry, Discrete Comput. Geom, vol.2, pp.195-222, 1987.

K. [. Clarkson, R. Mehlhorn, and . Seidel, Four results on randomized incremental constructions, Computational Geometry, vol.3, issue.4, pp.185-212, 1993.
DOI : 10.1016/0925-7721(93)90009-U

P. [. Clarkson and . Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, vol.1, issue.5, pp.387-421, 1989.
DOI : 10.1007/BF02187740

]. M. De-berg, O. Devillers, K. Dobrindt, and O. Schwarzkopf, Computing a single cell in the union of two simple polygons, Research Report, vol.2626, 1995.
URL : https://hal.archives-ouvertes.fr/inria-00074061

]. M. De-berg, K. Dobrindt, and O. Schwarzkopf, On lazy randomized incremental construction, Proc. 26th Annu. ACM Sympos. Theory Comput, pp.105-114, 1994.

]. O. Dev92 and . Devillers, Randomization yields simple O(n log * n) algorithms for difficult ?(n) problems. Internat, J. Comput. Geom. Appl, vol.2, issue.1, pp.97-111, 1992.

O. Devillers and M. Golin, Dog Bites Postman, Proc. 1st Annu. European Sympos. Algorithms (ESA '93), pp.133-144, 1993.
DOI : 10.1142/S0218195998000163
URL : https://hal.archives-ouvertes.fr/hal-01179730

O. Devillers, S. Meiser, and M. Teillaud, Fully dynamic delaunay triangulation in logarithmic expected time per operation, Computational Geometry, vol.2, issue.2, pp.55-80, 1992.
DOI : 10.1016/0925-7721(92)90025-N
URL : https://hal.archives-ouvertes.fr/hal-01180164

M. [. Devillers, M. Teillaud, and . Yvinec, Dynamic location in an arrangement of line segments in the plane, Algorithms Rev, vol.2, issue.3, pp.89-103, 1992.
URL : https://hal.archives-ouvertes.fr/inria-00413506

K. Dobrindt and M. Yvinec, Remembering conflicts in history yields dynamic algorithms, Proc. 4th Annu. Internat. Sympos. Algorithms Comput. (ISAAC 93), pp.21-30, 1993.
DOI : 10.1007/3-540-57568-5_231

L. J. Guibas, D. E. Knuth, and M. Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica, vol.134, issue.1-6, pp.381-413, 1992.
DOI : 10.1007/BF01758770

S. [. Mulmuley and . Sen, Dynamic point location in arrangements of hyperplanes, Proc. 7th Annu. ACM Sympos, pp.132-141, 1991.

]. K. Mul91a and . Mulmuley, On levels in arrangements and Voronoi diagrams, Discrete Comput. Geom, vol.6, pp.307-338, 1991.

]. K. Mul91b and . Mulmuley, Randomized multidimensional search trees: dynamic sampling, Proc. 7th Annu. ACM Sympos, pp.121-131, 1991.

]. K. Mul91c and . Mulmuley, Randomized multidimensional search trees: further results in dynamic sampling, Proc. 32nd Annu, pp.216-227, 1991.

]. K. Mul91d and . Mulmuley, Randomized multidimensional search trees: lazy balancing and dynamic shuffling, Proc. 32nd Annu, pp.180-196, 1991.

]. K. Mul93 and . Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, 1993.

]. M. Ovl81, J. Overmars, and . Van-leeuwen, Maintenance of configurations in the plane, J. Comput. Syst. Sci, vol.23, pp.166-204, 1981.

M. [. Preparata and . Shamos, Computational Geometry: an Introduction, 1985.
DOI : 10.1007/978-1-4612-1098-6

W. Pugh, Skip lists: a probabilistic alternative to balanced trees, Commun. ACM, vol.35, pp.668-676, 1990.

]. R. Sei91 and . Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Comput. Geom. Theory Appl, vol.1, pp.51-64, 1991.

]. M. Tei93 and . Teillaud, Towards dynamic randomized algorithms in computational geometry, Lecture Notes in Computer Science, vol.758, 1993.