Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Look at convex hull algorithms: en.wikipedia.org/wiki/Convex_hull_algorithms –  Matthew Kahle May 30 '13 at 13:54
add comment

1 Answer 1

up vote 4 down vote accepted

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)

share|improve this answer
    
Thanks a lot, Joseph. These pointers, especially the NP-hardness result, are extremely helpful. –  Stefan Kiefer May 30 '13 at 16:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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