New applications of random sampling in computational geometry
From MaRDI portal
Redirect page
Recommendations
Cites work
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 3261280 (Why is no real title available?)
- A linear algorithm for determining the separation of convex polyhedra
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Geometric retrieval problems
- Halfspace range search: An algorithmic application of k-sets
- How to search in history
- Learnability and the Vapnik-Chervonenkis dimension
- Multidimensional Searching Problems
- On k-Hulls and Related Problems
- On k-Nearest Neighbor Voronoi Diagrams in the Plane
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On the number of line separations of a finite set in the plane
- Polygon Retrieval
- Quicksort
- The maximum numbers of faces of a convex polytope
- Voronoi diagrams and arrangements
- Voronoi diagrams from convex hulls
- -nets and simplex range queries
Cited in
(99)- Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
- Discrepancy and approximations for bounded VC-dimension
- Multilevel polynomial partitions and simplified range searching
- The higher-order Voronoi diagram of line segments
- An algorithm for generalized point location and its applications
- The probabilistic method yields deterministic parallel algorithms
- On the number of regular vertices of the union of Jordan regions
- On partial covering for geometric set systems
- An upper bound on the number of planar K-sets
- Faster algorithms for next breakpoint and max value for parametric global minimum cuts
- A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
- Optimal randomized parallel algorithms for computational geometry
- A fast Las Vegas algorithm for triangulating a simple polygon
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
- On ray shooting in convex polytopes
- A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
- Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
- A randomized algorithm for fixed-dimensional linear programming
- Constructing arrangements optimally in parallel
- Algebraic \(k\)-sets and generally neighborly embeddings
- A deterministic view of random sampling and its use in geometry
- Dynamic half-space range reporting and its applications
- On the number of regular vertices of the union of Jordan regions
- Efficient ray shooting and hidden surface removal
- Point location among hyperplanes and unidirectional ray-shooting
- The complexity of many cells in arrangements of planes and related problems
- k-d darts, sampling by k-dimensional flat searches
- Relative neighborhood graphs in three dimensions
- On counting pairs of intersecting segments and off-line triangle range searching
- Minimizing the error of linear separators on linearly inseparable data
- Pointwise constraints in vector-valued Sobolev spaces. With applications in optimal control
- Almost tight bounds for -nets
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- Combinatorial complexity bounds for arrangements of curves and spheres
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- On vertical ray shooting in arrangements
- Separating and shattering long line segments
- On constant factors in comparison-based geometric algorithms and data structures
- Cutting hyperplanes for divide-and-conquer
- Implicitly representing arrangements of lines or segments
- The complexity and construction of many faces in arrangements of lines and of segments
- 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
- Applications of random sampling in computational geometry. II
- Randomized quickhull
- An efficient randomized algorithm for higher-order abstract Voronoi diagrams
- On the union of cylinders in three dimensions
- Lower bounds for semialgebraic range searching and stabbing problems
- Order-k -hulls and -shapes
- Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
- Lower bounds for semialgebraic range searching and stabbing problems
- The edge labeling of higher order Voronoi diagrams
- A new technique for analyzing substructures in arrangements of piecewise linear surfaces
- Applications of random sampling to on-line algorithms in computational geometry
- More dynamic data structures for geometric set cover with sublinear update time
- Lines in space: Combinatorics and algorithms
- Higher Order Voronoi Diagrams and Distance Functions in Art and Visualization
- Fast segment insertion and incremental construction of constrained Delaunay triangulations
- 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
- The \(k\)-nearest-neighbor Voronoi diagram revisited
- Algorithms for polytope covering and approximation
- A subexponential bound for linear programming
- Clamshell casting
- Random sampling with removal
- A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
- Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
- Space–Query-Time Tradeoff for Computing the Visibility Polygon
- Ray shooting on triangles in 3-space
- A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
- Lower envelopes of surface patches in 3-space
- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
- On geometric optimization with few violated constraints
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements
- Finding stabbing lines in 3-space
- An introduction to randomization in computational geometry
- Towards space efficient two-point shortest path queries in a polygonal domain
- Dynamic point location in arrangements of hyperplanes
- Almost tight upper bounds for lower envelopes in higher dimensions
- Robustness and Randomness
- Triangles in space or building (and analyzing) castles in the air
- A nearly parallel algorithm for the Voronoi diagram of a convex polygon
- Spanning trees with low crossing number
- An introduction to randomized algorithms
- Simplex Range Searching and Its Variants: A Review
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- An Output-Sensitive Convex Hull Algorithm for Planar Objects
- A note on point location in arrangements of hyperplanes
- Counting and representing intersections among triangles in three dimensions
- Streaming algorithms for extent problems in high dimensions
- On levels in arrangements and Voronoi diagrams
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Partitioning arrangements of lines. II: Applications
- Separating and shattering long line segments
- Union and split operations on dynamic trapezoidal maps
This page was built for publication: New applications of random sampling in computational geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1820582)
