A note on hyperplane generation (Q1328388)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on hyperplane generation |
scientific article |
Statements
A note on hyperplane generation (English)
0 references
2 January 1995
0 references
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.
0 references
point configurations
0 references
matroids
0 references
hyperplane generation
0 references
independence oracle
0 references
matroid algorithms
0 references