New applications of random sampling in computational geometry

DOI10.1007/BF02187879zbMath0615.68037MaRDI QIDQ1820582

Publication date: 1987

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131018

zbMATH Keywords

regions algorithms polytopes hyperplanes Voronoi diagram random sampling searching Bernoulli trials probability of success search structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Random convex sets and integral geometry (aspects of convex geometry) (52A22) Polytopes and polyhedra (52Bxx)

Related Items

Point location among hyperplanes and unidirectional ray-shooting, Efficient ray shooting and hidden surface removal, On lines missing polyhedral sets in 3-space, Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts, A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis, Ray shooting on triangles in 3-space, Almost tight upper bounds for lower envelopes in higher dimensions, Separating and shattering long line segments, The probabilistic method yields deterministic parallel algorithms, Dynamic half-space range reporting and its applications, A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, An introduction to randomization in computational geometry, Algorithms for polytope covering and approximation, Robustness and Randomness, Triangles in space or building (and analyzing) castles in the air, An algorithm for generalized point location and its applications, A note on point location in arrangements of hyperplanes, On geometric optimization with few violated constraints, A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams, Lines in space: Combinatorics and algorithms, Space–Query-Time Tradeoff for Computing the Visibility Polygon, A subexponential bound for linear programming, A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams, An efficient randomized algorithm for higher-order abstract Voronoi diagrams, A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model, Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location, On the union of cylinders in three dimensions, Minimizing the error of linear separators on linearly inseparable data, Simplex Range Searching and Its Variants: A Review, Approximating the k-Level in Three-Dimensional Plane Arrangements, Random sampling with removal, Partitioning arrangements of lines. I: An efficient deterministic algorithm, Combinatorial complexity bounds for arrangements of curves and spheres, Partitioning arrangements of lines. II: Applications, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, A non-linear lower bound for planar epsilon-nets, An introduction to randomized algorithms, Robust Tverberg and Colourful Carathéodory Results via Random Choice, An upper bound on the number of planar $K$-sets, Almost tight bounds for $\epsilon$-nets, Optimal randomized parallel algorithms for computational geometry, Randomized quickhull, On counting pairs of intersecting segments and off-line triangle range searching, Finding stabbing lines in 3-space, On the number of regular vertices of the union of Jordan regions, On ray shooting in convex polytopes, 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, On the number of regular vertices of the union of Jordan regions, Cutting hyperplanes for divide-and-conquer, The complexity and construction of many faces in arrangements of lines and of segments, The complexity of many cells in arrangements of planes and related problems, Pointwise constraints in vector-valued Sobolev spaces. With applications in optimal control, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, Spanning trees with low crossing number, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, Constructing arrangements optimally in parallel, On vertical ray shooting in arrangements, Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks, Higher Order Voronoi Diagrams and Distance Functions in Art and Visualization, Implicitly representing arrangements of lines or segments, A deterministic view of random sampling and its use in geometry, A nearly parallel algorithm for the Voronoi diagram of a convex polygon, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Applications of random sampling in computational geometry. II, A fast Las Vegas algorithm for triangulating a simple polygon, A randomized algorithm for fixed-dimensional linear programming, Clamshell casting, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, On Partial Covering For Geometric Set Systems, Union and split operations on dynamic trapezoidal maps, Counting and representing intersections among triangles in three dimensions, Unnamed Item, Streaming algorithms for extent problems in high dimensions, Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions, On levels in arrangements and Voronoi diagrams, The $k$-nearest-neighbor Voronoi diagram revisited, Discrepancy and approximations for bounded VC-dimension, On constant factors in comparison-based geometric algorithms and data structures, Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements, Order-$k$ $\alpha$-hulls and $\alpha$-shapes, An Output-Sensitive Convex Hull Algorithm for Planar Objects, IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS, Multilevel polynomial partitions and simplified range searching, Fast segment insertion and incremental construction of constrained Delaunay triangulations, Algebraic $k$-sets and generally neighborly embeddings, The higher-order Voronoi diagram of line segments

Uses Software

Quicksort

Cites Work