3
While there are probably much more efficient approaches, the following method can be used to compute the dimension in polynomial time, and is not too complicated.
Implicit inequalities
The dimension of a polyhedron $P$ is defined as the dimension of its affine hull, i.e. $\dim P := \dim \mathrm{aff}(P)$.
Let $a^i x \leq b_i$ for $i\in M$ be the linear ...
1
A similar question has been asked before, that may answer your question, here. Quoting the answer:
This is basically an instance of the line segment intersection problem. One standard approach is to use a sweep line algorithm. For instance, the Bentley-Ottman algorithm would be a reasonable choice, and is not too difficult to implement.
At each iteration ...
Only top voted, non community-wiki answers of a minimum length are eligible
