Couvrir un polygone simple avec des cercles

C'est ce que vous offre la grille coulissante ...

Merci pour votre réponse. Je connais plus ou moins les grilles coulissantes. Dans le scénario des points, il repose essentiellement sur le fait que dans chaque cellule de la grille, on peut résoudre le problème de couverture de manière optimale car chaque disque contient deux points sur sa frontière, plus le nombre de disques pour couvrir la cellule est limité. Ainsi, on peut le résoudre par la force brute. Mais dans le cadre d'un polygone, je ne vois pas comment résoudre le problème de manière optimale dans une cellule de la grille. Pourriez-vous donner quelques conseils à ce sujet?

Les grilles coulissantes impliquent qu'à l'intérieur de la cellule de la grille, la taille de la solution est petite. Ensuite, vous devez résoudre le problème à l'intérieur de chaque cellule de la grille (généralement exactement) en utilisant un autre algorithme. Voici une autre façon d'y penser - échantillonnez le polygone de manière très dense, puis résolvez votre problème sur l'échantillon ... Et oui, les détails exacts de la façon de procéder peuvent être assez douloureux ... Donc, supposons que vous ayez un polygone avec n arêtes, et vous savez que la solution optimale est de taille k. Savez-vous comment résoudre le problème exactement dans ce cas?

Merci encore. Après réflexion, je ne sais toujours pas comment couvrir le polygone de manière optimale avec k disques, même si je connais k. Le fait qu'il y ait peu de nature discrète rend la couture très difficile pour moi. Quant à votre approche d'échantillonnage: après l'échantillonnage, aimeriez-vous alors ne couvrir que la partie échantillonnée? Ne sommes-nous pas alors confrontés au problème de gaspiller beaucoup de disques pour combler les lacunes?

$N \times N$$N=O(k/\epsilon)$$\epsilon$