Fourier-Motzkin elimination in two variables

Write the constraints of a two-variable system as $a_i x + b_i y \ge c_i$ for $i < m$, where $a_i = A_{i0}$ and $b_i = A_{i1}$. Then the system has a solution $(x,y) \in \mathbb{R}^2$ if and only if the following one-variable system in the unknown $t$ has a solution:

This is Fourier–Motzkin elimination of the variable $y$. In one direction, each inequality of the reduced system is a nonnegative combination of the original ones: the pair inequality is $(-b_j)$ times constraint $i$ plus $b_i$ times constraint $j$, in which the $y$ terms cancel. In the other direction, a solution $t$ of the reduced system is extended to a solution of the original one by choosing $y$ between the largest lower bound $\max_{b_i>0}(c_i - a_i t)/b_i$ and the smallest upper bound $\min_{b_j<0}(c_j - a_j t)/b_j$; the pair inequalities say exactly that every lower bound is at most every upper bound, and the degenerate cases where one or both families are empty are immediate.

The reduced system has at most $m + m^2/4$ inequalities in one variable, so the elimination turns a two-variable feasibility question into a one-variable one at quadratic cost. Combined with a one-variable decision procedure it gives a polynomial-time algorithm for two-variable linear programming in a machine model with indirect addressing, which is the first nontrivial case of the fixed-dimension results of Megiddo and Dyer. For the general problem the elimination is of no use, since eliminating $n$ variables in turn can square the number of constraints each time; that blow-up is precisely why Smale's ninth problem is not settled by this classical method.