Applications of random sampling in computational geometry. II
From MaRDI portal
Publication:1823685
DOI10.1007/BF02187740zbMATH Open0681.68060OpenAlexW4254977685MaRDI QIDQ1823685FDOQ1823685
Authors: Kenneth L. Clarkson, Peter W. Shor 
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131089
Recommendations
- An optimal convex hull algorithm in any fixed dimension
- scientific article; zbMATH DE number 431985
- Applications of random sampling to on-line algorithms in computational geometry
- Randomized incremental construction of Delaunay and Voronoi diagrams
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- scientific article; zbMATH DE number 177830
- scientific article; zbMATH DE number 1256644
- Randomized geometric algorithms and pseudorandom generators
- An introduction to randomization in computational geometry
- A fast Las Vegas algorithm for triangulating a simple polygon
Cites Work
- Quicksort
- Title not available (Why is that?)
- \(\epsilon\)-nets and simplex range queries
- New applications of random sampling in computational geometry
- Title not available (Why is that?)
- The power of geometric duality
- Linear Programming in Linear Time When the Dimension Is Fixed
- Combinatorial complexity bounds for arrangements of curves and spheres
- Title not available (Why is that?)
- An optimal algorithm for intersecting line segments in the plane
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Title not available (Why is that?)
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- The Ultimate Planar Convex Hull Algorithm?
- On k-Hulls and Related Problems
- Halfspace range search: An algorithmic application of k-sets
- On the shape of a set of points in the plane
- Convex hulls of finite sets of points in two and three dimensions
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- More on k-sets of finite sets in the plane
- Title not available (Why is that?)
- Finding the intersection of two convex polyhedra
- On the number of k-subsets of a set of n points in the plane
- The number of small semispaces of a finite set of points in the plane
- A fast Las Vegas algorithm for triangulating a simple polygon
- Optimal randomized parallel algorithms for computational geometry
Cited In (only showing first 100 items - show all)
- On random cartesian trees
- All Farthest Neighbors in the Presence of Highways and Obstacles
- Space-efficient planar convex hull algorithms
- The higher-order Voronoi diagram of line segments
- CONFLICT-FREE COLORINGS OF SHALLOW DISCS
- On the complexity of higher order abstract Voronoi diagrams
- A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
- A Polynomial-Time Algorithm for Computing Shortest Paths of Bounded Curvature Amidst Moderate Obstacles
- APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
- On ray shooting in convex polytopes
- Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
- Efficient searching with linear constraints
- Bregman Voronoi diagrams
- A deterministic view of random sampling and its use in geometry
- Abstract Voronoi diagrams revisited
- Faster geometric algorithms via dynamic determinant computation
- On counting pairs of intersecting segments and off-line triangle range searching
- How hard is half-space range searching?
- Minimizing the error of linear separators on linearly inseparable data
- Efficient randomized algorithms for some geometric optimization problems
- Computing a single cell in the overlay of two simple polygons
- Combinatorial complexity bounds for arrangements of curves and spheres
- An optimal convex hull algorithm in any fixed dimension
- On enclosing k points by a circle
- Separating and shattering long line segments
- Four results on randomized incremental constructions
- Randomized incremental construction of abstract Voronoi diagrams
- A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
- Two proofs for shallow packings
- Repeated angles in the plane and related problems
- Cutting hyperplanes for divide-and-conquer
- On range searching with semialgebraic sets
- On the construction of abstract Voronoi diagrams
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
- Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
- Efficient and robust persistent homology for measures
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- New applications of random sampling in computational geometry
- Fast linear expected-time algorithms for computing maxima and convex hulls
- On the union of cylinders in three dimensions
- Title not available (Why is that?)
- Almost optimal set covers in finite VC-dimension
- Approximation algorithms for maximum independent set of pseudo-disks
- Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
- Incremental topological flipping works for regular triangulations
- \(k\)-violation linear programming
- Entering and leaving \(j\)-facets
- A new technique for analyzing substructures in arrangements of piecewise linear surfaces
- Randomized incremental construction of Delaunay and Voronoi diagrams
- Applications of random sampling to on-line algorithms in computational geometry
- Output-sensitive results on convex hulls, extreme points, and related problems
- Lines in space: Combinatorics and algorithms
- Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- On the union of fat wedges and separating a collection of segments by a line
- Points and triangles in the plane and halving planes in space
- The \(k\)-nearest-neighbor Voronoi diagram revisited
- Computing hereditary convex structures
- From proximity to utility: a Voronoi partition of Pareto optima
- Relative \((p,\varepsilon )\)-approximations in geometry
- Crossing patterns of semi-algebraic sets
- Union of random Minkowski sums and network vulnerability analysis
- On the \(k\)-colored rainbow sets in fixed dimensions
- Euclidean minimum spanning trees and bichromatic closest pairs
- Delaunay refinement algorithms for triangular mesh generation
- On geometric optimization with few violated constraints
- A semi-algebraic version of Zarankiewicz's problem
- Certifying algorithms
- The overlay of lower envelopes and its applications
- Classroom examples of robustness problems in geometric computations
- Witnessed \(k\)-distance
- Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements
- Almost tight upper bounds for lower envelopes in higher dimensions
- An Output-Sensitive Convex Hull Algorithm for Planar Objects
- Optimal partition trees
- An introduction to randomized algorithms
- Counting and representing intersections among triangles in three dimensions
- Algebraic properties of location problems with one circular barrier.
- Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
- TetGen, a Delaunay-based quality tetrahedral mesh generator
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- Topological relations between separating circles
- FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
- The Clarkson–Shor Technique Revisited and Extended
- On the complexity of randomly weighted multiplicative Voronoi diagrams
- Near-linear approximation algorithms for geometric hitting sets
- Cutting lemma and Zarankiewicz's problem in distal structures
- ``The big sweep: On the power of the wavefront approach to Voronoi diagrams
- Four results on randomized incremental constructions
- Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
- Parallel geometric algorithms for multi-core computers
- On pseudo-disk hypergraphs
- Abstract Voronoi diagram in 3-space
- An upper bound on the number of planar \(K\)-sets
- The number of edges of many faces in a line segment arrangement
- Randomized geometric algorithms and pseudorandom generators
- A fast Las Vegas algorithm for triangulating a simple polygon
- On range searching with semialgebraic sets
- Practical methods for shape fitting and kinetic data structures using coresets
- Dynamic connectivity for axis-parallel rectangles
This page was built for publication: Applications of random sampling in computational geometry. II
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823685)
