Skip to main content
2 of 2
replaced deprecated tag 'geometry'
Ricardo Andrade
  • 6.2k
  • 5
  • 42
  • 69

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?