4
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

6
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ Thanks a lot, Joseph. These pointers, especially the NP-hardness result, are extremely helpful. $\endgroup$ May 30, 2013 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.