@Article{YR80,
author = { Andrew C. Yao and Ronald L. Rivest },
title = { On the polyhedral decision problem },
journal = { SIAM J. Computing },
issn = { 0097-5397 },
OPTyear = { 1980 },
OPTmonth = { May },
date = { 1980-05 },
volume = { 9 },
number = { 2 },
pages = { 343--347 },
keywords = { adversary strategy, complexity, dimension, edge, face, linear
decision tree, lower bound, polyhedron },
doi = { 10.1137/0209028 },
abstract = {
Computational problems sometimes can be cast in the following form:
Given a point $\mathbf{x}$ in $R^n$, determine if $\mathbf{x}$ lies
in some fixed polyhedron. In this paper we give a general lower bound
to the complexity of such problems, showing that $\frac{1}{2} \log_2 f_s$
linear comparisons are needed in the worst case, for any polyhedron with
$f_s$ $s$-dimensional faces. For polyhedra with abundant faces, this leads
to lower bounds nonlinear in $n$, the number of variables.
},
}