Applications of random sampling to on-line algorithms in computational geometry
From MaRDI portal
Publication:1192610
DOI10.1007/BF02293035zbMath0769.68118MaRDI QIDQ1192610
Monique Teillaud, Olivier Devillers, Mariette Yvinec, Jean-Daniel Boissonnat, René Schott
Publication date: 27 September 1992
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131209
on-line algorithmsVoronoi diagramsconvex hullsarrangements of curves in the planedesign and randomized analysis of geometric algorithmsline segments in the plane
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis, Computing a single cell in the overlay of two simple polygons, Separating and shattering long line segments, Densest packings of typical convex sets are not lattice-like, Piecewise linear paths among convex obstacles, An introduction to randomization in computational geometry, A compact piecewise-linear Voronoi diagram for convex sites in the plane, Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, On-line construction of the upper envelope of triangles and surface patches in three dimensions, An algorithm for constructing the convex hull of a set of spheres in dimension \(d\), Randomized geometric algorithms and pseudorandom generators, Dynamic well-spaced point sets, Markov incremental constructions, Randomized incremental construction of abstract Voronoi diagrams, Four results on randomized incremental constructions, Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection, Fully dynamic Delaunay triangulation in logarithmic expected per operation, THE DELAUNAY HIERARCHY, On the randomized construction of the Delaunay tree, FURTHEST SITE ABSTRACT VORONOI DIAGRAMS, THE SHUFFLING BUFFER, Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, On lazy randomized incremental construction, Four results on randomized incremental constructions, Union and split operations on dynamic trapezoidal maps, A Complete Implementation for Computing General Dimensional Convex Hulls, Dog Bites Postman
Cites Work
- Higher-dimensional Voronoi diagrams in linear expected time
- Combinatorial complexity bounds for arrangements of curves and spheres
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- On the randomized construction of the Delaunay tree
- Applications of random sampling in computational geometry. II
- A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
- An optimal algorithm for intersecting line segments in the plane
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
