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?)
- A Randomized Algorithm for Closest-Point Queries
- A deterministic view of random sampling and its use in geometry
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- An optimal convex hull algorithm in any fixed dimension
- Applications of random sampling in computational geometry. II
- Construction of \(\epsilon\)-nets
- Cutting hyperplane arrangements
- Implicitly representing arrangements of lines or segments
- Linear Programming in Linear Time When the Dimension Is Fixed
- Linear Time Algorithms for Two- and Three-Variable Linear Programs
- Linear programming in \(O(n\times 3^{d^2})\) time
- New applications of random sampling in computational geometry
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Partitioning arrangements of lines. II: Applications
- Point location among hyperplanes and unidirectional ray-shooting
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Range searching with efficient hierarchical cuttings
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- -nets and simplex range queries
Cited in
(81)- Algorithms for bichromatic line-segment problems and polyhedral terrains
- New lower bounds for Hopcroft's problem
- Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
- On counting point-hyperplane incidences
- The exact fitting problem in higher dimensions
- CUTTINGS AND APPLICATIONS
- Cutting hyperplane arrangements
- Decomposable multi-parameter matroid optimization problems.
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
- On ray shooting in convex polytopes
- On range searching with semialgebraic sets
- Approximating the packedness of polygonal curves
- A deterministic view of random sampling and its use in geometry
- Cuttings for disks and axis-aligned rectangles in three-space
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- On the number of regular vertices of the union of Jordan regions
- Robust shape fitting via peeling and grating coresets
- On counting pairs of intersecting segments and off-line triangle range searching
- Range searching with efficient hierarchical cuttings
- Computing the maximum overlap of two convex polygons under translations
- scientific article; zbMATH DE number 637334 (Why is no real title available?)
- A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
- Efficient partition trees
- On vertical ray shooting in arrangements
- An optimal convex hull algorithm in any fixed dimension
- Nearly time-optimal kernelization algorithms for the line-cover problem with big data
- Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment
- Vertical decompositions for triangles in 3-space
- Weak visibility counting in simple polygons
- Algorithms for subpath convex hull queries and ray-shooting among segments
- On range searching with semialgebraic sets
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Improved upper bounds for approximation by zonotopes
- An affine invariant \(k\)-nearest neighbor regression estimate
- Almost optimal set covers in finite VC-dimension
- Fitting a step function to a point set with outliers based on simplicial thickness data structures
- Multiple Cuts in Separating Plane Algorithms
- Efficient algorithms for maximum regression depth
- Optimal algorithms for geometric centers and depth
- The complexity of cutting complexes
- Improved points approximation algorithms based on simplicial thickness data structures
- Covering lattice points by subspaces and counting point-hyperplane incidences
- Output-sensitive results on convex hulls, extreme points, and related problems
- Fast separator decomposition for finite element meshes
- Maximum overlap and minimum convex hull of two convex polyhedra under translations
- A deterministic algorithm for the three-dimensional diameter problem
- Constructing Planar Cuttings in Theory and Practice
- Subquadratic encodings for point configurations
- A new asymmetric inclusion region for minimum weight triangulation
- Linear-space data structures for range mode query in arrays
- Evasive sets, covering by subspaces, and point-hyperplane incidences
- Reporting intersecting pairs of convex polytopes in two and three dimensions
- Approximate input sensitive algorithms for point pattern matching
- Clamshell casting
- On fat partitioning, fat covering and the union size of polygons
- A note on hyperplane generation
- Space–Query-Time Tradeoff for Computing the Visibility Polygon
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Partial hyperplane activation for generalized intersection cuts
- A semi-algebraic version of Zarankiewicz's problem
- Approximations and optimal geometric divide-and-conquer
- Fast Combinatorial Algorithm for Tightly Separating Hyperplanes
- A survey of mass partitions
- Finding simplices containing the origin in two and three dimensions
- The 2-center problem in three dimensions
- Hypergraph Cuts with General Splitting Functions
- Optimal partition trees
- On optimal cuts of hyperrectangles
- Simplex Range Searching and Its Variants: A Review
- COMPUTING CLOSEST POINTS FOR SEGMENTS
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- A note on point location in arrangements of hyperplanes
- Reporting bichromatic segment intersections from point sets
- Stability versus speed in a computable algebraic model
- scientific article; zbMATH DE number 512824 (Why is no real title available?)
- Removing depth-order cycles among triangles: an algorithm generating triangular fragments
- Minimum-width double-slabs and widest empty slabs in high dimensions
- Counting the number of crossings in geometric graphs
- Optimal slope selection via cuttings
- An efficient algorithm for the three-dimensional diameter problem
This page was built for publication: Cutting hyperplanes for divide-and-conquer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1209837)
