scientific article; zbMATH DE number 4151829

MaRDI QIDQ3481216zbMATH OpenFDO

Authors Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir

Publication date 1989

zbMATH Keywords

decompositiongeneralized point location problemstratification of real semi-algebraic sets

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Computational aspects of higher-dimensional varieties (14Q15) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Some aspects of complexity in real algebraic geometry
• scientific article; zbMATH DE number 66679
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Some speed-ups and speed limits for real algebraic geometry

Cited in

(26)

• Extremal problems on triangle areas in two and three dimensions
• Cutting hyperplane arrangements
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Applications of a new space-partitioning technique
• Almost tight upper bounds for lower envelopes in higher dimensions
• \(L^3\) estimates for an algebraic variable coefficient Wolff circular maximal function
• The overlay of lower envelopes and its applications
• Vertical decompositions for triangles in 3-space
• Lines in space: Combinatorics and algorithms
• Point location in zones of \(k\)-flats in arrangements
• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Weaving patterns of lines and line segments in space
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• Crossing patterns of semi-algebraic sets
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
• On ray shooting for triangles in 3-space and related problems
• On range searching with semialgebraic sets
• Diameter, width, closest line pair, and parametric searching
• On ray shooting in convex polytopes
• Combinatorial bounds in distal structures
• On the computation of an arrangement of quadrics in 3D
• Lower envelopes of surface patches in 3-space
• Triangulating a nonconvex polytope

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3481216)