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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references