zbMATH — the first resource for mathematics

A note on hyperplane generation. (English) Zbl 0803.05015
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.

05B35 Combinatorial aspects of matroids and geometric lattices
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
Full Text: DOI