如何用不连续的半径恒定的圆覆盖平面中的一组圆？

Question

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 :)

Answer 1

根据补丁和孔的大小，可能没有解决方案。

具有最紧凑补丁阵列的解决方案：

没有解决方案，因为洞比补丁大，这允许未覆盖的区域：

没有解决方案，因为孔太近：

对于一般结构，您可以从以孔为中心的补丁开始。然后根据需要平移并旋转（围绕连续面片的中心）面片：