HAL - INRIA :: [inria-00090675, version 1] Applications of random sampling to on-line algorithms in computational geometry

inria-00090675, version 1

Applications of random sampling to on-line algorithms in computational geometry

Jean-Daniel Boissonnat () ¹, Olivier Devillers ()^a^, 1, René Schott^b^, 2, Monique Teillaud ()^a^, 1, Mariette Yvinec () ¹

Discrete & Computational Geometry 8, 1 (1992) 51--71

Résumé : 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.

a – INRIA
b – Université Henri Poincaré - Nancy I
1 : PRISME (INRIA Sophia Antipolis)
INRIA
2 : Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine

inria-00090675, version 1
http://hal.inria.fr/inria-00090675
oai:hal.inria.fr:inria-00090675
Contributeur : Olivier Devillers <>
Soumis le : Vendredi 1 Septembre 2006, 16:10:06
Dernière modification le : Vendredi 1 Septembre 2006, 16:41:46

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00090675"><analytic>
<author><persName><forename>Jean-Daniel</forename><surname>Boissonnat</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Devillers</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>René</forename><surname>Schott</surname></persName>
<affiliation>
<orgName type="laboratory">LORIA</orgName>
<orgName type="team">Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Monique</forename><surname>Teillaud</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Mariette</forename><surname>Yvinec</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<title type="main" level="a">Applications of random sampling to on-line algorithms in computational geometry</title></analytic><monogr><title level="j" type="main">Discrete & Computational Geometry</title><imprint><publisher>Springer</publisher><biblScope type="publicationDate">1992-00-00</biblScope><biblScope type="vol">8</biblScope><biblScope type="issue">1</biblScope><biblScope type="pp">51--71</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00090675</idno><idno type="HALFile">http://hal.inria.fr/inria-00090675/PDF/paper.pdf</idno></biblStruct>
</listBibl>
</listBibl>