A note on hyperplane generation

DOI10.1006/JCTB.1994.1033MaRDI QIDQ1328388zbMATH OpenOpenAlexFDO

Authors Paul Seymour

Publication date 2 January 1995

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1994.1033

zbMATH Keywords

hyperplane generationindependence oraclematroid algorithmsmatroidspoint configurations

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• Constructing Arrangements of Lines and Hyperplanes with Applications
• Output-sensitive cell enumeration in hyperplane arrangements
• scientific article; zbMATH DE number 1383707
• Cutting hyperplanes for divide-and-conquer
• scientific article; zbMATH DE number 1182912

Cited in

(8)

• Computing the spark: mixed-integer programming for the (vector) matroid girth problem
• Which nonnegative matrices are slack matrices?
• a-tint: a polymake extension for algorithmic tropical intersection theory
• On the (co)girth of a connected matroid
• From the zonotope construction to the Minkowski addition of convex polytopes
• Unique key Horn functions
• scientific article; zbMATH DE number 4125543 (Why is no real title available?)
• Algorithmic aspects of partial convexity

This page was built for publication: A note on hyperplane generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1328388)