On computing a set of points meeting every cell defined by a family of polynomials on a variety

DOI10.1006/jcom.1997.0434zbMath0872.68050OpenAlexW2118184814MaRDI QIDQ1361873

Saugata Basu, Richard Pollack, Marie-Françoise Roy

Publication date: 28 July 1997

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.1997.0434

zbMATH Keywords

Basu-Pollack-Roy algorithmBen-Or-Kozen-Reif algorithm

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Convex transversals, Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics, Refined bounds on the number of connected components of sign conditions on a variety, Shape matching by random sampling, Deformation techniques for efficient polynomial equation solving., A certificate for semidefinite relaxations in computing positive-dimensional real radical ideals, Approximately matching polygonal curves with respect to the Fréchet distance, On a real analog of Bezout inequality and the number of connected components of sign conditions, Computing roadmaps of semi-algebraic sets on a variety, Geometric optimization and sums of algebraic functions

Cites Work

• 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
• The complexity of elementary algebra and geometry
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• On the combinatorial and algebraic complexity of quantifier elimination
• On the number of cells defined by a family of polynomials on a variety