Lower bound on testing membership to a polyhedron by algebraic decision and computation trees

DOI10.1007/BF02770873zbMath0871.68176OpenAlexW2045871238MaRDI QIDQ677021

Marek Karpinski, Dima Yu. Grigoriev, Nikolaj N. jun. Vorob'ev

Publication date: 23 March 1997

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02770873

zbMATH Keywords

convex polyhedraalgebraic decisioncomputation trees

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

A lower bound for randomized algebraic decision trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving systems of polynomial inequalities in subexponential time
• Counting connected components of a semialgebraic set in subexponential time
• Complexity of deciding Tarski algebra
• Finding irreducible components of some real transcendental varieties
• Complexity lower bounds for computation trees with elementary transcendental function gates
• Lower bounds for arithmetic networks. II: Sum of Betti numbers
• Lower bounds on testing membership to a polyhedron by algebraic decision trees
• On the Polyhedral Decision Problem
• Differential Topology
• Linear Decision Trees, Subspace Arrangements, and Mobius Functions
• On the Betti Numbers of Real Varieties
• Decision tree complexity and Betti numbers