  The problem of detecting and removing redundant constraints is fundamental in
optimization. We focus on the case of linear programs (LPs), given by $d$
variables with $n$ inequality constraints. A constraint is called
\emph{redundant}, if after its removal, the LP still has the same feasible
region. The currently fastest method to detect all redundancies is due to
Clarkson: it solves $n$ linear programs, but each of them has at most $s$
constraints, where $s$ is the number of nonredundant constraints.
  In this paper, we study the special case where every constraint has at most
two variables with nonzero coefficients. This family, denoted by $LI(2)$, has
some nice properties. Namely, as shown by Aspvall and Shiloach, given a
variable $x_i$ and a value $\lambda$, we can test in time $O(nd)$ whether there
is a feasible solution with $x_i = \lambda$. Hochbaum and Naor present an
$O(d^2 n \log n)$ algorithm for solving the feasibility problem in $LI(2)$.
Their technique makes use of the Fourier-Motzkin elimination method and the
earlier mentioned result by Aspvall and Shiloach.
  We present a strongly polynomial algorithm that solves redundancy detection
in time $O(n d^2 s \log s)$. It uses a modification of Clarkson's algorithm,
together with a revised version of Hochbaum and Naor's technique. Finally we
show that dimensionality testing can be done with the same running time as
solving feasibility.
