On the Geometry and Computational Complexity of Radon Partitions in the Iinteger Lattice

DOI10.1137/0404039zbMath0735.52007OpenAlexW2011116511MaRDI QIDQ3979444

Shmuel Onn

Publication date: 26 June 1992

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0404039

zbMATH Keywords

growthcomputational complexityinteger programminginteger latticeRadon numberRadon partitions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Integer programming (90C10) Axiomatic and generalized convexity (52A01) Inequalities and extremum problems involving convexity in convex geometry (52A40) Helly-type theorems and geometric transversal theory (52A35)

Related Items

Transversal numbers over subsets of linear spaces, Quantitative Tverberg theorems over lattices and other discrete sets, Oriented matroid polytopes and polyhedral fans are signable, On weak \(\epsilon\)-nets and the Radon number, Colourful linear programming, Unnamed Item, Tverberg’s theorem is 50 years old: A survey, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Tverberg theorems over discrete sets of points, Transversal numbers for hypergraphs arising in geometry, A fractional Helly theorem for convex lattice sets