A deterministic view of random sampling and its use in geometry

DOI10.1007/BF02122778zbMath0715.68036MaRDI QIDQ751816

Bernard Chazelle, Joel Friedman

Publication date: 1990

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

geometric algorithmsrandom samplingdivide-and-conquer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random convex sets and integral geometry (aspects of convex geometry) (52A22)

Related Items (68)

Tighter estimates for \(\epsilon\)-nets for disks ⋮ An efficient \(k\) nearest neighbors searching algorithm for a query line. ⋮ Time-space trade-offs for triangulations and Voronoi diagrams ⋮ On range searching with semialgebraic sets ⋮ Point location among hyperplanes and unidirectional ray-shooting ⋮ On lines missing polyhedral sets in 3-space ⋮ Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ The probabilistic method yields deterministic parallel algorithms ⋮ Time-Space Trade-offs for Triangulations and Voronoi Diagrams ⋮ Geometric Hitting Sets for Disks: Theory and Practice ⋮ Bounding the piercing number ⋮ Cuttings for disks and axis-aligned rectangles in three-space ⋮ From proximity to utility: a Voronoi partition of Pareto optima ⋮ A survey of mass partitions ⋮ Almost optimal set covers in finite VC-dimension ⋮ Vertical decompositions for triangles in 3-space ⋮ Optimal, output-sensitive algorithms for constructing planar hulls in parallel ⋮ Lines in space: Combinatorics and algorithms ⋮ Improved upper bounds for approximation by zonotopes ⋮ The exact fitting problem in higher dimensions ⋮ A deterministic algorithm for the three-dimensional diameter problem ⋮ Randomized geometric algorithms and pseudorandom generators ⋮ On Ray Shooting for Triangles in 3-Space and Related Problems ⋮ A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model ⋮ Indexing moving points ⋮ Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location ⋮ A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space ⋮ Decomposable multi-parameter matroid optimization problems. ⋮ A center transversal theorem for hyperplanes and applications to graph drawing ⋮ Optimal partition trees ⋮ Simplex Range Searching and Its Variants: A Review ⋮ One-Sided Epsilon-Approximants ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ Unnamed Item ⋮ On a Question of Bourgain about Geometric Incidences ⋮ Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications ⋮ Cutting hyperplane arrangements ⋮ A singly exponential stratification scheme for real semi-algebraic varieties and its applications ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Robust Tverberg and Colourful Carathéodory Results via Random Choice ⋮ On disjoint concave chains in arrangements of (pseudo) lines ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ On separating points by lines ⋮ Near optimal bounds for the Erdős distinct distances problem in high dimensions ⋮ Farthest neighbors, maximum spanning trees and related problems in higher dimensions ⋮ Reporting points in halfspaces ⋮ Intersection queries in sets of disks ⋮ Range searching with efficient hierarchical cuttings ⋮ Efficient partition trees ⋮ Dynamic point location in arrangements of hyperplanes ⋮ Relative neighborhood graphs in three dimensions ⋮ Quasi-optimal upper bounds for simplex range searching and new zone theorems ⋮ A note on the number of different inner products generated by a finite set of vectors ⋮ Cutting hyperplanes for divide-and-conquer ⋮ RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS ⋮ An Upper Bound on the k-Modem Illumination Problem ⋮ Optimal deterministic algorithms for 2-d and 3-d shallow cuttings ⋮ Planar point sets determine many pairwise crossing segments ⋮ On vertical ray shooting in arrangements ⋮ On regular vertices of the union of planar convex objects ⋮ Unnamed Item ⋮ On range searching with semialgebraic sets ⋮ Counting and representing intersections among triangles in three dimensions ⋮ An optimal convex hull algorithm in any fixed dimension ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions ⋮ Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems ⋮ IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity and construction of many faces in arrangements of lines and of segments
• \(\epsilon\)-nets and simplex range queries
• On the ratio of optimal integral and fractional covers
• Implicitly representing arrangements of lines or segments
• On a set of almost deterministic k-independent random variables
• New applications of random sampling in computational geometry
• Puncture sets
• On the density of families of sets
• Constructing Arrangements of Lines and Hyperplanes with Applications
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Randomized Algorithm for Closest-Point Queries
• Explicit codes with low covering radius
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: A deterministic view of random sampling and its use in geometry