Let's say I have a 3D space containing spheres (for simplicity, all with the same radius). All spheres are in two disjoint sets, $A$ and $B$. It is guaranteed that spheres from $A$ do not intersect with spheres from $B$.

How can I find the smallest possible set $C$ of spheres (of any radius) that covers all spheres from $A$ (i.e. $\cup A\subset\cup C$) but not even partially covering any spheres from $B$ (i.e. $\cup C \cap \cup B = \emptyset$)?

If it is relevant whether the surface of a sphere is included in its points, I suppose the simplest case to implement (if required) is all open spheres (i.e. without their surface). That means it is safe if spheres from $C$ "touch" spheres from $B$ (but with zero intersection volume still).

The trivial answer is $C=A$, but I am looking for an answer that uses the least number of spheres (whose radii are not limited in any way). The spheres in $C$ may also intersect with each other freely. If possible, polynomial algorithm is preferred.

  • $\begingroup$ Some ideas: start by checking whether pairs of spheres can be covered by a sphere with intersecting bad ones and replace them by the smallest sphere that covers them (this one's unique) and see if that can be covered by another sphere, etc. This procedure could be order dependent, in which case you have to pick the correct order... somehow. To efficiently check which spheres can be covered, you should use a data structure that takes in account the 'locality' of the spheres; perhaps a sweep line approach would work. $\endgroup$ – Discrete lizard Dec 13 '17 at 18:11

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.