Skip to main content

Efficiently determine if convex hull contains the unit ball

Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time? The convex hull itself might have an exponential number of facets so we cannot afford explicitly to compute it.

My main interest is not in computer precision so we can make whatever assumptions help avoid that in relation to the points themselves (for example they only have integer coordinates).

Simd
  • 3.4k
  • 26
  • 54