<p>Consider the following optimization problem:</p>

<p><strong>Input</strong>: a 3-dimensional "object" $O$.</p>

<p><strong>Output</strong>: 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$.</p>

<p>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? </p>

CC BY-SA 3.0
2016-05-19T01:31:41.280Z
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?
Sariel Har-Peled
CC BY-SA 3.0
2016-05-19T08:18:54.187Z
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).
Paramar
CC BY-SA 3.0
2016-05-19T15:07:40.793Z
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
Sasho Nikolov
CC BY-SA 3.0
2016-05-19T16:01:16.120Z
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.
Paramar
CC BY-SA 3.0
2016-05-19T19:59:18.783Z
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: http://arxiv.org/abs/cs/0604008.
Sariel Har-Peled
CC BY-SA 3.0
2016-05-19T21:47:49.943Z
It is not clear what you mean by object. You have to fix the representation of it and explain how it is given to the algorithm. E.g. it is a convex object given be a set of vertices, by a set of inequalities, a non-convex polytope, etc.
Kaveh
CC BY-SA 3.0
2016-05-19T21:50:27.413Z
Also it was not clear whether you want to count the space covered by more than one circle only once or multiple times. Based on your comments I edited it to count them only once, change $(\bigcup_i S_i) - O$ to $\Sigma_i \mathsf{vol}(S_i - O)$ if you want to count them multiple times.
Kaveh
CC BY-SA 3.0
2016-05-21T00:27:36.423Z
The concept of [Hausdorff dimension](https://en.wikipedia.org/wiki/Hausdorff_dimension) seems like it might be related, as it connects the idea of "waste-minimizing covering by small spheres" to "dimension=3".
Andrew Morgan
<ds.algorithms><reference-request><computational-geometry><covering-problems>
Trade-off between number of spheres and wasted space in covering a 3d object by spheres
Paramar
# Trade-off between number of spheres and wasted space in covering a 3d object by spheres

(Asked by: username_0 on 2016-05-18)

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?

**Tags:** ds.algorithms, reference-request, computational-geometry, covering-problems
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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).  
> **username_2**: 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  
> **username_0**: 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.  
> **username_1**: 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: http://arxiv.org/abs/cs/0604008.  
> **username_3**: It is not clear what you mean by object. You have to fix the representation of it and explain how it is given to the algorithm. E.g. it is a convex object given be a set of vertices, by a set of inequalities, a non-convex polytope, etc.  
> **username_3**: Also it was not clear whether you want to count the space covered by more than one circle only once or multiple times. Based on your comments I edited it to count them only once, change $(\bigcup_i S_i) - O$ to $\Sigma_i \mathsf{vol}(S_i - O)$ if you want to count them multiple times.  
> **username_4**: The concept of [Hausdorff dimension](https://en.wikipedia.org/wiki/Hausdorff_dimension) seems like it might be related, as it connects the idea of "waste-minimizing covering by small spheres" to "dimension=3".  

---

## 0 answers

