# Tag Info

This can be done in $O(N log(N))$ time, where $N$ is the number of rows in $A$. The matrix inequality $Ax \leq b$ is equivalent to half-plane inequalities: $(a_i, x) \leq b_i, i = 1, \ldots, N$. We can obtain the vertices of polygon that is the intersection of these half-planes by the following procedure: Transform lines $\{(a_i, x) = b_i\} \mapsto d_i$ ...