0
$\begingroup$

Consider the following optimization problem:

Input: a 3-dimensional "object" $O$.

Output: a covering of $O$ by a list of $k$ spheres $S_1, \ldots, S_k$ (given by their centers and radii) minimizing the volume of $(\bigcup_i S_i) - O$.

Increasing $k$ results in better optimum (smaller wasted space). I am interest in the trade-off between $k$ and the optimum wasted space. Has this problem been studied before?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ So, you are give a set of balls, and a set, and you want to find the subsets of the balls, such that their union cover the set, and the total volume of the union is minimized? $\endgroup$ – Sariel Har-Peled May 19 '16 at 1:31
  • $\begingroup$ There is no predefined set of balls. You can create the arbitrary spheres you need. You want to cover the whole 3d object, but without covering too much unneeded space. (for example a giant sphere pretty much covers anything, but leaves a lot of empty space. A better solution would probably be a union of smaller balls). $\endgroup$ – Paramar May 19 '16 at 8:18
  • $\begingroup$ Is the number of balls or their radius fixed? Otherwise, as you observe, the optimal solution would take a very large number of balls, of very small radius $\endgroup$ – Sasho Nikolov May 19 '16 at 15:07
  • $\begingroup$ As I already said I would like to know if the trade-off is studied( and possibly a change in complexity, which happens sometimes in parameterized problems). But for the sake of the conversation let's say that we want only 3 spheres, to make life easier. $\endgroup$ – Paramar May 19 '16 at 16:01
  • 3
    $\begingroup$ One can get a constant approximation to the total volume covered using shifted quadtrees, and dynamic programming. The details are not easy at all. See here for a remotely relevant paper: arxiv.org/abs/cs/0604008. $\endgroup$ – Sariel Har-Peled May 19 '16 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.