Hot answers tagged

2

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$ ...


1

Perhaps start here and work backward and forward in time using Google scholar: G√ľnther, Oliver, and Eugene Wong. "A dual approach to detect polyhedral intersections in arbitrary dimensions." BIT Numerical Mathematics 31.1 (1991): 2-14. PDF download.



Only top voted, non community-wiki answers of a minimum length are eligible