Skip to main content
2 of 2
Corrected spelling and grammar.
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$

Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-spaces in $\mathbb R^d$. This is the $H$-representation of $P$.

Question. In terms of $n$ and $d$, what is a good upper-bound on the number of half-spaces in the smallest $H$-representation of $P$ ?

dohmatob
  • 6.9k
  • 1
  • 18
  • 76