A deterministic view of random sampling and its use in geometry
From MaRDI portal
Publication:751816
DOI10.1007/BF02122778zbMath0715.68036MaRDI QIDQ751816
Bernard Chazelle, Joel Friedman
Publication date: 1990
Published in: Combinatorica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Random convex sets and integral geometry (aspects of convex geometry) (52A22)
Related Items
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
