caa a22 4500 469074922 CHVBK 20180323132932.0 cr unu---uuuuu 170328e19920701xx s 000 0 eng 10.1007/BF02293035 doi (NATIONALLICENCE)springer-10.1007/BF02293035 Applications of random sampling to on-line algorithms in computational geometry [Elektronische Daten] [Jean-Daniel Boissonnat, Olivier Devillers, René Schott, Monique Teillaud, Mariette Yvinec] This paper presents a general framework for the design and randomized analysis of geometric algorithms. These algorithms are on-line and the framework provides general bounds for their expected space and time complexities when averaging over all permutations of the input data. The method is general and can be applied to various geometric problems. The power of the technique is illustrated by new efficient on-line algorithms for constructing convex hulls and Voronoi diagrams in any dimension, Voronoi diagrams of line segments in the plane, arrangements of curves in the plane, and others. Springer-Verlag New York Inc., 1992 Boissonnat Jean-Daniel INRIA, 2004 Route des Lucioles, B.P. 109, 06561, Valbonne Cédex, France aut Devillers Olivier INRIA, 2004 Route des Lucioles, B.P. 109, 06561, Valbonne Cédex, France aut Schott René CRIN, B.P. 239, 54506, Vandoeuvre, France aut Teillaud Monique INRIA, 2004 Route des Lucioles, B.P. 109, 06561, Valbonne Cédex, France aut Yvinec Mariette LIENS, CNRS URA 1327, 45 rue d'Ulm, 75230, Paris Cédex 05, France aut Discrete & Computational Geometry Springer New York 8/1(1992-07-01), 51-71 0179-5376 8:1<51 1992 8 454 https://doi.org/10.1007/BF02293035 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293035 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Boissonnat Jean-Daniel INRIA, 2004 Route des Lucioles, B.P. 109, 06561, Valbonne Cédex, France aut NATIONALLICENCE 700 1- Devillers Olivier INRIA, 2004 Route des Lucioles, B.P. 109, 06561, Valbonne Cédex, France aut NATIONALLICENCE 700 1- Schott René CRIN, B.P. 239, 54506, Vandoeuvre, France aut NATIONALLICENCE 700 1- Teillaud Monique INRIA, 2004 Route des Lucioles, B.P. 109, 06561, Valbonne Cédex, France aut NATIONALLICENCE 700 1- Yvinec Mariette LIENS, CNRS URA 1327, 45 rue d'Ulm, 75230, Paris Cédex 05, France aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/1(1992-07-01), 51-71 0179-5376 8:1<51 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer