A deterministic view of random sampling and its use in geometry
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 4152425 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 3685495 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- A Randomized Algorithm for Closest-Point Queries
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Explicit codes with low covering radius
- Implicitly representing arrangements of lines or segments
- New applications of random sampling in computational geometry
- On a set of almost deterministic k-independent random variables
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On the density of families of sets
- On the ratio of optimal integral and fractional covers
- Puncture sets
- The complexity and construction of many faces in arrangements of lines and of segments
- -nets and simplex range queries
Cited in
(74)- Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
- On separating points by lines
- Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
- Tighter estimates for -nets for disks
- A note on the number of different inner products generated by a finite set of vectors
- Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
- An efficient \(k\) nearest neighbors searching algorithm for a query line.
- The probabilistic method yields deterministic parallel algorithms
- The exact fitting problem in higher dimensions
- Cutting hyperplane arrangements
- Faster algorithms for next breakpoint and max value for parametric global minimum cuts
- Decomposable multi-parameter matroid optimization problems.
- A note about weak -nets for axis-parallel boxes in d-space
- Deterministic sampling and range counting in geometric data streams
- Randomized geometric algorithms and pseudorandom generators
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
- On range searching with semialgebraic sets
- An upper bound on the k-modem illumination problem
- Time-space trade-offs for triangulations and Voronoi diagrams
- Time-space trade-offs for triangulations and Voronoi diagrams
- On a Question of Bourgain about Geometric Incidences
- Cuttings for disks and axis-aligned rectangles in three-space
- Point location among hyperplanes and unidirectional ray-shooting
- Relative neighborhood graphs in three dimensions
- On counting pairs of intersecting segments and off-line triangle range searching
- Range searching with efficient hierarchical cuttings
- Indexing moving points
- Efficient partition trees
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- On vertical ray shooting in arrangements
- An optimal convex hull algorithm in any fixed dimension
- Vertical decompositions for triangles in 3-space
- Reporting points in halfspaces
- On ray shooting for triangles in 3-space and related problems
- Cutting hyperplanes for divide-and-conquer
- On regular vertices of the union of planar convex objects
- On range searching with semialgebraic sets
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- On lines missing polyhedral sets in 3-space
- Robust Tverberg and Colourful Carathéodory Results via Random Choice
- Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
- Improved upper bounds for approximation by zonotopes
- New applications of random sampling in computational geometry
- Almost optimal set covers in finite VC-dimension
- Geometric hitting sets for disks: theory and practice
- Lower bounds for semialgebraic range searching and stabbing problems
- Lower bounds for semialgebraic range searching and stabbing problems
- scientific article; zbMATH DE number 7378732 (Why is no real title available?)
- Lines in space: Combinatorics and algorithms
- A deterministic algorithm for the three-dimensional diameter problem
- Optimal, output-sensitive algorithms for constructing planar hulls in parallel
- A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- A non-linear lower bound for planar epsilon-nets
- From proximity to utility: a Voronoi partition of Pareto optima
- RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
- Near optimal bounds for the Erdős distinct distances problem in high dimensions
- Lower envelopes of surface patches in 3-space
- A center transversal theorem for hyperplanes and applications to graph drawing
- On disjoint concave chains in arrangements of (pseudo) lines
- A survey of mass partitions
- Bounding the piercing number
- Semialgebraic range stabbing, ray shooting, and intersection counting in the plane
- Dynamic point location in arrangements of hyperplanes
- Intersection queries in sets of disks
- One-sided epsilon-approximants
- Optimal partition trees
- Simplex Range Searching and Its Variants: A Review
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- Counting and representing intersections among triangles in three dimensions
- Tight lower bounds on the VC-dimension of geometric set systems
- Farthest neighbors, maximum spanning trees and related problems in higher dimensions
- Near-optimal lower bounds for -nets for half-spaces and low complexity set systems
This page was built for publication: A deterministic view of random sampling and its use in geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751816)
