Let $P$ be a given finite set of points within the $n$dimensional unit cube. A finite set $Q$ of points within the $n$dimensional unit cube covers $P$ if $conv(Q) \supseteq P$ where $conv(Q)$ denotes the convex hull of $Q$. How can one compute a minimal set $Q$ that covers $P$? Trivially, a minimal set $Q$ satisfies $Q \le P$ and $Q \le 2^n$. The minimal size could be computed by appealing to decision procedures for the firstorder theory of the reals, but is there a smarter way?

This is not a direct answer, but a closely related problem is known to be NPhard:
This paper establishes several results, including this:
This question was first posed by Victor Klee, and I coauthored a paper that provided an efficient algorithm in $\mathbb{R}^2$. But the above result shows it is already intractable in $\mathbb{R}^3$. I do not remember the DasGoodrich proof well enough to know if it can achieve the same result with the outer polyhedron a cube. There are many approximation algorithms available, as this is an important practical problem. For example:


