A note on hyperplane generation (Q1328388): Difference between revisions

This short and elegant note describes an algorithm that generates all the hyperplanes spanned by a finite point set \(X\) ``at a polynomial rate''. That is, although the set \(\mathcal H\) of hyperplanes may have exponential size, the first \(i\) hyperplanes in \(\mathcal H\) are generated in a number of steps that is polynomial in \(i\) and the size of the input. In particular, one can check whether a given list of hyperplanes is complete, in a time that is polynomial in \(| X|+ |{\mathcal H}|\), the number of points plus the number of hyperplanes. The proof is based on a matroid formulation of the problem: ``The introduction of matroid theory here is just for clarity and maximum generality, but later, in the proof, the use of matroid theory is essential.'' A problem of Lovász that motivated this note, how to check whether a list \(\mathcal H\) of hyperplanes completely describes the convex hull of \(X\), remains open.