So you have a sheet / area of a given dimension, and within this area are holes (their center point(x,y) and radius are given). The problem is you need to cover these holes with patches. These circular patches have a fixed radius (ie: radius of 5) and are not allowed to overlap with each other (but can touch). You're allowed to use as many as you like, the goal is not to find the most optimal number, but to see if it's possible to cover every single hole.

I've solved a similar problem with a KD tree, but due to the 3D dimensional nature of the holes in this problem, I'm unsure on how to approach it. Just looking for a pointer in the right direction, not the coded solution :)

| cite | improve this question | | | | |
  • $\begingroup$ 3D nature? Is the radius the third "dimension"? $\endgroup$ – Peter Taylor May 9 '19 at 6:33
  • $\begingroup$ 3D might be the wrong word, but because the holes aren't simply "points" (they're circles that vary in size, so they have not only a x,y center, but a radius too), I'm unsure how you would sort them if you were to use a KD tree. I've only ever used a KD tree for standard 2D points (x,y) $\endgroup$ – Ryan May 9 '19 at 6:36
  • $\begingroup$ Would you mind adding a sketch of your algorithm for points? $\endgroup$ – Peter Taylor May 9 '19 at 9:10
  • $\begingroup$ I guess the radius of the hole is smaller than the one of the patches (just to be sure)? $\endgroup$ – Seb Destercke May 9 '19 at 11:18
  • $\begingroup$ One simple observation: If every hole has strictly positive diameter, then no solution can involve a patch partially overlapping a hole, since in that case the part of the hole that is not covered by that patch must be covered by at least 1 other patch, and on either side of the point where it touches the first patch is a wedge-shaped area of the hole that is too narrow to be covered by any patch. $\endgroup$ – j_random_hacker May 9 '19 at 12:32