convex polyhedron in the unit cube 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 $\operatorname{conv}(Q) \supseteq P$ where $\operatorname{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 first-order theory of the reals, but is there a smarter way?
 A: This is not a direct answer, but a closely related problem is known to be NP-hard:

Das, Goodrich.
  "On the Complexity of Approximating and Illuminating Three-Dimensional Convex Polyhedra."
  1995. (ACM link; PDF download)

This paper establishes several results, including this:

Theorem 4.2. The problem of fitting a polyhedron with a minimum number of faces between 
  two given nested convex polyhedra is NP-hard. 

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 Das-Goodrich 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:

Mitchell, Suri. "Separation and approximation of polyhedral surfaces."
  In Proc. 3rd ACM-SIAM Sympos. Discrete Algorithms, pages 296-306, 1992. (CiteSeer link)

