Applications of random sampling in computational geometry. II
From MaRDI portal
Publication:1823685
The paper is an excellent overview about several ``Las Vegas-algorithms given by the authors. Some results are improvements of results given by the first author in an earlier paper \textit{K.L. Clarkson} [Discrete Comput. Geom. 2, 195-222 (1987; Zbl 0615.68037)]. Random sampling is used for several new geometric algorithms. The central lemma formulated at the beginning gives sharp bounds for the use of random subsets. Such subsets can be used for divide and conquer and for some incremental techniques. Some interesting results and algorithms are the following: An 0(A \(+\) n log n)-expected time and 0(n)-space-algorithm reports all the A intersecting pairs of a set of n line segments in the plane. An 0(n log n)-expected time algorithm computes the convex hull of n points in \(E^ 3\) (for \(d>3:\) \(0(n^{\lfloor d/2\rfloor}))\). An 0(n log n)-expected time algorithm computes the diameter of a set of n points in \(E^ 3\). Algorithms for halfspace range reporting and a simple proof for bounds on high-order Voronoi diagrams are given. In the concluding remarks relations with deterministic algorithms and possible extensions are discussed.
Recommendations
- An optimal convex hull algorithm in any fixed dimension
- scientific article; zbMATH DE number 431985
- Applications of random sampling to on-line algorithms in computational geometry
- Randomized incremental construction of Delaunay and Voronoi diagrams
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase(\le k)-Levels in Three Dimensions
- scientific article; zbMATH DE number 177830
- scientific article; zbMATH DE number 1256644
- Randomized geometric algorithms and pseudorandom generators
- An introduction to randomization in computational geometry
- A fast Las Vegas algorithm for triangulating a simple polygon
Cites work
- -nets and simplex range queries
- A fast Las Vegas algorithm for triangulating a simple polygon
- An optimal algorithm for intersecting line segments in the plane
- Combinatorial complexity bounds for arrangements of curves and spheres
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Convex hulls of finite sets of points in two and three dimensions
- Finding the intersection of two convex polyhedra
- Halfspace range search: An algorithmic application of k-sets
- scientific article; zbMATH DE number 3122839 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 3755865 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- Linear Programming in Linear Time When the Dimension Is Fixed
- More on k-sets of finite sets in the plane
- New applications of random sampling in computational geometry
- On k-Hulls and Related Problems
- On the number of k-subsets of a set of n points in the plane
- On the shape of a set of points in the plane
- Optimal randomized parallel algorithms for computational geometry
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Quicksort
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- The number of small semispaces of a finite set of points in the plane
- The power of geometric duality
- The Ultimate Planar Convex Hull Algorithm?
Cited in
(only showing first 100 items - show all)- Depth of segments and circles through points enclosing many points: A note
- Practical methods for shape fitting and kinetic data structures using coresets
- Dynamic connectivity for axis-parallel rectangles
- Kinetic hanger
- Euclidean minimum spanning trees and bichromatic closest pairs
- Small-dimensional linear programming and convex hulls made easy
- Points and triangles in the plane and halving planes in space
- On \(k\)-sets in arrangements of curves and surfaces
- An introduction to randomized algorithms
- On disjoint concave chains in arrangements of (pseudo) lines
- An upper bound on the number of planar K-sets
- Randomized incremental construction of Delaunay and Voronoi diagrams
- Repeated angles in the plane and related problems
- Applications of random sampling to on-line algorithms in computational geometry
- Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
- Farthest neighbors, maximum spanning trees and related problems in higher dimensions
- Dynamic point location in arrangements of hyperplanes
- Fully dynamic Delaunay triangulation in logarithmic expected per operation
- The number of edges of many faces in a line segment arrangement
- Relative neighborhood graphs in three dimensions
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Fast linear expected-time algorithms for computing maxima and convex hulls
- Seven fingers allow force-torque closure grasps on any convex polyhedron
- Cutting hyperplanes for divide-and-conquer
- On the randomized construction of the Delaunay tree
- The widest k-dense corridor problems
- An approximate algorithm for computing multidimensional convex hulls
- An optimal convex hull algorithm in any fixed dimension
- An invariant property of balls in arrangements of hyperplanes
- A bound on local minima of arrangements that implies the upper bound theorem
- Arrangements of oriented hyperplanes
- On the union of fat wedges and separating a collection of segments by a line
- \(k\)-sets and random hulls
- Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements
- On the sum of squares of cell complexities in hyperplane arrangements
- On range searching with semialgebraic sets
- Point location among hyperplanes and unidirectional ray-shooting
- Castles in the air revisited
- k-violation linear programming
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
- Almost tight upper bounds for lower envelopes in higher dimensions
- On the complexity of some basic problems in computational convexity. I. Containment problems
- Derandomizing an output-sensitive convex hull algorithm in three dimensions
- An introduction to randomization in computational geometry
- The common exterior of convex polygons in the plane
- Optimal, output-sensitive algorithms for constructing planar hulls in parallel
- Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
- Erased arrangements of linear and convex decompositions of polyhedra
- Indexing moving points
- Computing farthest neighbors on a convex polytope.
- Algebraic properties of location problems with one circular barrier.
- Efficient searching with linear constraints
- Delaunay refinement algorithms for triangular mesh generation
- Time-space trade-offs for triangulations and Voronoi diagrams
- Computing a minimum-width square or rectangular annulus with outliers
- On the union complexity of families of axis-parallel rectangles with a low packing number
- A crossing lemma for Jordan curves
- Untangling planar curves
- Minimizing the diameter of a spanning tree for imprecise points
- Optimal deterministic shallow cuttings for 3-d dominance ranges
- Finding pairwise intersections inside a query range
- Local polyhedra and geometric graphs
- Constructing the convex hull of a partially sorted set of points
- Efficient randomized algorithms for some geometric optimization problems
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- Output-sensitive results on convex hulls, extreme points, and related problems
- A new technique for analyzing substructures in arrangements of piecewise linear surfaces
- New applications of random sampling in computational geometry
- A fast Las Vegas algorithm for triangulating a simple polygon
- Union and split operations on dynamic trapezoidal maps
- Robot motion planning and the single cell problem in arrangements
- On computing the diameter of a point set in high dimensional Euclidean space.
- Reporting intersecting pairs of convex polytopes in two and three dimensions
- Abstract Voronoi diagram in 3-space
- Dynamic half-space range reporting and its applications
- Largest \(j\)-simplices in \(n\)-polytopes
- A time-optimal parallel algorithm for three-dimensional convex hulls
- On geometric optimization with few violated constraints
- Almost tight upper bounds for the single cell and zone problems in the three dimensions
- Almost optimal set covers in finite VC-dimension
- The overlay of lower envelopes and its applications
- Vertical decompositions for triangles in 3-space
- Incremental topological flipping works for regular triangulations
- Lines in space: Combinatorics and algorithms
- 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\)
- Point location in zones of \(k\)-flats in arrangements
- A deterministic algorithm for the three-dimensional diameter problem
- Randomized geometric algorithms and pseudorandom generators
- Witnessed k-distance
- Convex hulls of spheres and convex hulls of disjoint convex polytopes
- The 2-center problem in three dimensions
- A quick negative selection algorithm for one-class classification in big data era
- Faster approximate diameter and distance oracles in planar graphs
- On the complexity of the \(k\)-level in arrangements of pseudoplanes
- Union of hypercubes and 3D Minkowski sums with random sizes
- Active-learning a convex body in low dimensions
- Randomized incremental construction of Delaunay triangulations of nice point sets
- Polyhedral circuits and their applications
- On circles enclosing many points
This page was built for publication: Applications of random sampling in computational geometry. II
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823685)
