  The problem of detecting and removing redundant constraints is fundamental in
optimization. We focus on the case of linear programs (LPs) in dictionary form,
given by $n$ equality constraints in $n+d$ variables, where the variables are
constrained to be nonnegative. A variable $x_r$ is called redundant, if after
removing $x_r \geq 0$ the LP still has the same feasible region. The time
needed to solve such an LP is denoted by $LP(n,d)$.
  It is easy to see that solving $n+d$ LPs of the above size is sufficient to
detect all redundancies. The currently fastest practical method is the one by
Clarkson: it solves $n+d$ linear programs, but each of them has at most $s$
variables, where $s$ is the number of nonredundant constraints.
  In the first part we show that knowing all of the finitely many dictionaries
of the LP is sufficient for the purpose of redundancy detection. A dictionary
is a matrix that can be thought of as an enriched encoding of a vertex in the
LP. Moreover - and this is the combinatorial aspect - it is enough to know only
the signs of the entries, the actual values do not matter. Concretely we show
that for any variable $x_r$ one can find a dictionary, such that its sign
pattern is either a redundancy or nonredundancy certificate for $x_r$.
  In the second part we show that considering only the sign patterns of the
dictionary, there is an output sensitive algorithm of running time
$\mathcal{O}(d \cdot (n+d) \cdot s^{d-1} \cdot LP(s,d) + d \cdot s^{d} \cdot
LP(n,d))$ to detect all redundancies. In the case where all constraints are in
general position, the running time is $\mathcal{O}(s \cdot LP(n,d) + (n+d)
\cdot LP(s,d))$, which is essentially the running time of the Clarkson method.
Our algorithm extends naturally to a more general setting of arrangements of
oriented topological hyperplane arrangements.
