LOWER-BOUND ON TESTING MEMBERSHIP TO A POLYHEDRON BY ALGEBRAIC DECISION AND COMPUTATION TREES

Authors
GRIGORIEV D KARPINSKI M VOROBJOV N
Citation
D. Grigoriev et al., LOWER-BOUND ON TESTING MEMBERSHIP TO A POLYHEDRON BY ALGEBRAIC DECISION AND COMPUTATION TREES, Discrete & computational geometry, 17(2), 1997, pp. 191-215
Citations number
26
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
17
Issue
2
Year of publication
1997
Pages
191 - 215
Database
ISI
SICI code
0179-5376(1997)17:2<191:LOTMTA>2.0.ZU;2-7
Abstract
We introduce a new method of proving lower bounds on the depth of alge braic d-degree decision (resp. computation) trees and apply it to prov e a lower bound Omega (log N) (resp. Omega (log N/log log N)) for test ing membership to an n-dimensional convex polyhedron having N faces of all dimensions, provided that N > (nd)(Omega(n)) (resp. N > n(Omega(n ))). This bound apparently does not follow from the methods developed by Ben-Or, Bjorner, Lovasz, and Yao [1], [4], [24] because topological invariants used in these methods become trivial for convex polyhedra.