A singly exponential stratification scheme for real semi-algebraic varieties and its applications
From MaRDI portal
Publication:1177933
DOI10.1016/0304-3975(91)90261-YzbMath0757.14031OpenAlexW2058889860MaRDI QIDQ1177933
Bernard Chazelle, Micha Sharir, Leonidas J. Guibas, Herbert Edelsbrunner
Publication date: 26 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(91)90261-y
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Semialgebraic sets and related spaces (14P10)
Related Items
On range searching with semialgebraic sets, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Computing the Betti numbers of arrangements via spectral sequences, A semi-algebraic version of Zarankiewicz's problem, Straight-path queries in trajectory data, Vertical decomposition of arrangements of hyperplanes in four dimensions, Cuttings for disks and axis-aligned rectangles in three-space, Nondegenerate spheres in four dimensions, Subquadratic algorithms for algebraic 3SUM, A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing, Geometric pattern matching in d-dimensional space, Semi-algebraic Ramsey numbers, Throwing a sofa through the window, Approximating length-restricted means under dynamic time warping, Approximating the k-Level in Three-Dimensional Plane Arrangements, The Schur-Erdős problem for semi-algebraic colorings, Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications, How to find groups?, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Cutting hyperplanes for divide-and-conquer, On the computation of an arrangement of quadrics in 3D, Motion planning via manifold samples, Unnamed Item, Unnamed Item, Cutting lemma and Zarankiewicz's problem in distal structures, A near-linear algorithm for the planar segment-center problem, Efficient randomized algorithms for some geometric optimization problems, Notes on the complexity of exact view graph algorithms for piecewise smooth algebraic surfaces, Bounded \(VC\)-dimension implies the Schur-Erdős conjecture, Smoothed analysis of probabilistic roadmaps, Faster algorithms for growing prioritized disks and rectangles, An exact and efficient approach for computing a cell in an arrangement of quadrics, Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
- A deterministic view of random sampling and its use in geometry
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- Elementary structure of real algebraic varieties
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Triangulating a nonconvex polytope
- Some dynamic computational geometry problems
- \(\epsilon\)-nets and simplex range queries
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Some techniques for geometric searching with implicit set representations
- Solving systems of polynomial inequalities in subexponential time
- Real quantifier elimination is doubly exponential
- New applications of random sampling in computational geometry
- An inequality for the discriminant of a polynomial
- An algorithm for generalized point location and its applications
- Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
- Optimal Point Location in a Monotone Subdivision
- Searching and storing similar lists
- On Approximations and Incidence in Cylindrical Algebraic Decompositions
- A Randomized Algorithm for Closest-Point Queries
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- On Euclid's Algorithm and the Theory of Subresultants
- On the Betti Numbers of Real Varieties
