Three-dimensional polyhedra can be described by three polynomial inequalities

2008/07/14 by Gennadiy Averkov, Averkov, Gennadiy, Martin Henk +1
Computer Science · Mathematics · #14P05 #14Q99 #52A20 #52B11 #Advanced Combinatorial Mathematics #Algebraic Geometry (math.AG) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.0807.2137

openalex publication_date 2008/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Bosse et al. conjectured that for every natural number d ≥ 2 and every d-dimensional polytope P in \real^d there exist d polynomials p₀(x),...,p_d-1(x) satisfying P=\x ∈ ℝ^d : p₀(x) ≥ 0, >..., p_d-1(x) ≥ 0 \. We show that for dimensions d ≤ 3 even every d-dimensional polyhedron can be described by d polynomial inequalities. The proof of our result is constructive.

Citations

• Representing elementary semi-algebraic sets by a few polynomial inequalities: A constructive approach

Related

• Polynomial inequalities representing polyhedra
• On the representation of polyhedra by polynomial inequalities
• Minimal polynomial descriptions of polyhedra and special semialgebraic sets
• Representing simple d-dimensional polytopes by d polynomials
• A simple proof of tail--polynomial bounds on the diameter of polyhedra