Return to Question

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).

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 (in both $n$ and $d$)? 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).

Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball 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).

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).