Applications of random sampling in computational geometry. II
From MaRDI portal
Publication:1823685
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
- scientific article; zbMATH DE number 3122839 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 3755865 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- A fast Las Vegas algorithm for triangulating a simple polygon
- An optimal algorithm for intersecting line segments in the plane
- Combinatorial complexity bounds for arrangements of curves and spheres
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Convex hulls of finite sets of points in two and three dimensions
- Finding the intersection of two convex polyhedra
- Halfspace range search: An algorithmic application of k-sets
- Linear Programming in Linear Time When the Dimension Is Fixed
- More on k-sets of finite sets in the plane
- New applications of random sampling in computational geometry
- On k-Hulls and Related Problems
- On the number of k-subsets of a set of n points in the plane
- On the shape of a set of points in the plane
- Optimal randomized parallel algorithms for computational geometry
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Quicksort
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- The Ultimate Planar Convex Hull Algorithm?
- The number of small semispaces of a finite set of points in the plane
- The power of geometric duality
- -nets and simplex range queries
Cited in
(only showing first 100 items - show all)- Computing farthest neighbors on a convex polytope.
- The Clarkson–Shor Technique Revisited and Extended
- Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
- Sublinear Geometric Algorithms
- Near-linear approximation algorithms for geometric hitting sets
- GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS
- COMPUTING THE DIAMETER OF A POINT SET
- Two approaches to building time-windowed geometric data structures
- On a problem of Danzer
- Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
- A unified approach to tail estimates for randomized incremental construction
- Space-efficient planar convex hull algorithms
- On random cartesian trees
- On lazy randomized incremental construction
- Cutting lemma and Zarankiewicz's problem in distal structures
- Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
- All Farthest Neighbors in the Presence of Highways and Obstacles
- Geometric Streaming Algorithms with a Sorting Primitive
- ``The big sweep: On the power of the wavefront approach to Voronoi diagrams
- Parallel geometric algorithms for multi-core computers
- The higher-order Voronoi diagram of line segments
- On pseudo-disk hypergraphs
- Four results on randomized incremental constructions
- A quick negative selection algorithm for one-class classification in big data era
- An upper bound on the number of planar K-sets
- The number of edges of many faces in a line segment arrangement
- Abstract Voronoi diagram in 3-space
- CONFLICT-FREE COLORINGS OF SHALLOW DISCS
- A fast Las Vegas algorithm for triangulating a simple polygon
- Practical methods for shape fitting and kinetic data structures using coresets
- On Exact Computation of Tukey Depth Central Regions
- Randomized geometric algorithms and pseudorandom generators
- On ray shooting in convex polytopes
- On the complexity of higher order abstract Voronoi diagrams
- Dynamic connectivity for axis-parallel rectangles
- A finite algorithm for the realizabilty of a Delaunay triangulation
- A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
- An approximate algorithm for computing multidimensional convex hulls
- Pargeo: a library for parallel computational geometry
- Geometric Packing under Nonuniform Constraints
- Derandomizing an output-sensitive convex hull algorithm in three dimensions
- On range searching with semialgebraic sets
- Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
- 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
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Algorithms for marketing-mix optimization
- Efficient searching with linear constraints
- Time-space trade-offs for triangulations and Voronoi diagrams
- Covering many or few points with unit disks
- Fully dynamic Delaunay triangulation in logarithmic expected per operation
- Time-space trade-offs for triangulations and Voronoi diagrams
- Faster approximate diameter and distance oracles in planar graphs
- Algebraic \(k\)-sets and generally neighborly embeddings
- The maximum-level vertex in an arrangement of lines
- A deterministic view of random sampling and its use in geometry
- Bregman Voronoi diagrams
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- Dynamic half-space range reporting and its applications
- 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
- Abstract Voronoi diagrams revisited
- On Center Regions and Balls Containing Many Points
- Faster geometric algorithms via dynamic determinant computation
- Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications
- Computing the multicover bifiltration
- Constructing the convex hull of a partially sorted set of points
- 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
- How hard is half-space range searching?
- Computing a minimum-width square or rectangular annulus with outliers
- The maximum exposure problem
- Indexing moving points
- scientific article; zbMATH DE number 7559117 (Why is no real title available?)
- Abstract Voronoi diagrams from closed bisecting curves
- Computing a single cell in the overlay of two simple polygons
- Reprint of: Delaunay refinement algorithms for triangular mesh generation
- Efficient randomized algorithms for some geometric optimization problems
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- On the union complexity of families of axis-parallel rectangles with a low packing number
- Improved approximation bounds for the minimum constraint removal problem
- Randomized incremental construction of Delaunay triangulations of nice point sets
- Combinatorial complexity bounds for arrangements of curves and spheres
- Decomposition of Multiple Packings with Subquadratic Union Complexity
- An optimal convex hull algorithm in any fixed dimension
- Separating and shattering long line segments
- Finding pairwise intersections inside a query range
- Optimal deterministic shallow cuttings for 3-d dominance ranges
- On enclosing k points by a circle
- Four results on randomized incremental constructions
- Randomized incremental construction of abstract Voronoi diagrams
- On the randomized construction of the Delaunay tree
- Convex hulls of spheres and convex hulls of disjoint convex polytopes
- A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
- Vertical decompositions for triangles in 3-space
- On constant factors in comparison-based geometric algorithms and data structures
- On the B-differential of the componentwise minimum of two affine vector functions
- Two proofs for shallow packings
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)
