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 first-order theory of the reals, but is there a smarter way?

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?