Recouvrement "minimal" d'une surface

[alphattm]

Bonjour à tous,

Je cherche des informations ou des travaux/idées concernant un domaine que je souhaite utiliser dans mon TIPE. Le problème est de recouvrir une surface donnée avec le moins de cercle possibles, ceux ci pouvant déborder. Les cercles ayant TOUS LE MEME RAYON. Je souhaite obtenir dans un premier temps des résultats sur des surfaces simples : rectangles, carrés, disques ...

Merci d'avance

PS : l'objectif à long terme est d'obtenir un moyen ou une méthode pour obtenir le même résultat en disproportionnant volontairement les cercles, par exemple en en prenant la moitié de rayons deux fois plus grands etc ...

Re Merci

[kazeriahm]

je comprends pas :

si tu peux deborder, tu te mets a l'interieur de ta surface, tu prends un seul cercle, de diametre suffisament grand

et bim, ca fait des chocapics

[Maks]

Bonjour,
je te conseille de chercher du côté de la géode. Cela peut faire une bonne introduction au sujet.

Bon courage.

[Maks]

Tu souhaites utiliser un nombre fini de disques ?

[Maks]

Il veut peut-être minimiser l'aire débordante. Enfin ça paraîtrait logique.

[Zavonen]

Pour que le problème ait un sens il faut que le diamètre commun des cercles du recouvrement soit une donnée primaire. A mon avis c'est bien expliqué dans le post original.
Le problème n'est pas recouvrir la surface avec un minimum de cercles quel que soit le rayon, mais recouvrir la surface avec un minimum de cercles de rayon donné (autrement dit comment disposer les centres). Ce qui a l'air d'être assez ardu.
On trouvera toujours des solutions même pour un simple rectangle (un treillis) mais savoir si ces solutions sont optimales.

[alphattm]

dernier post gagne le grolo c'est exactement ça ... imagine un carré de coté 1, je veux le recouvrir avec des cercles de rayon 0.2 .... combien m'en faut-il minimum ...

ça résume en gros le problème

sauf que je veux le faire avec autre chose que des carrés par exemples, il me semble que la taille même du rayon joue .... d'où la complexité, j'ai essayé de trouver des trucs en pensant au recouvrement de la France par les antennes de téléphonies par exemples, mais j'ai pas trouvé grand chose, en tout cas j'en ai discuté avec mon prof de maths et c'est à peu près certains que des travaux ont été mené ... reste à les trouver ^^

[Zavonen]

On peut peut-être commencer simplement avec la figure formée par trois cercles dont les centres forment un triangle équilatéral. dans ce cas, si on veut que la figure recouverte soit connexe, il faut que les centres soient distants de racine(3).
Partons donc d'une triangulation du plan par un réseau dont les sommets de triangles comme ci-dessus.
Pour un rectangle donné il est facile de calculer le nombre de sommets du réseau inclus à l'intérieur (on pourra utiliser l'indice d'un point par rapport à un lacet qui est ici un simple polygone). Une première optimisation consisterait à déplacer le rectangle pour qu'il englobe le moins de sommets possible du réseau.
On n'est évidemment pas sûr qu'il s'agisse d'une optimisation absolue, mais même ainsi la chose n'est pas évidente.
Cela peut être un point de départ.

[benfis]

[FONT=Franklin Gothic Medium]voila qui est clair[/FONT] :dodo:

[Maks]

C'est sûr que ce sont des choses difficiles à expliquer sans schéma.

[alphattm]

stop !!! je pense "voir" l'idée, mais je comprends pas certains mots ( et oui je suis juste en maths sup, fin passe en maths spé )

connexe = ?

indice d'un point par rapport à un lacet = ??

Sinon je vois plus ou moins ce que tu veux faire et ton idée me plait bien, de mon coté je planchais sur quelque chose pour trouver le nombre minimal théorique de cercles de mêmes rayons. J'expose ce que je pense :
rapport de l'aire de la surface sur aire d'un cercle de rayon R donné donne un nombre qui si on prend sa partie entière et ajoute 1 donne un nombre minimal de disques. On n'ajouterai pas 1 si le quotient est déjà un entier ...

Vous en pensez quoi ?

=> edit : quoi que non ça marche pas ..... je compte pas mes recouvrements entre cercles, obligatoires, enfin ça donne une idée du nombre de cercles, surement à un quelque chose près selon la taille de la figure

[Zavonen]

connexe = ?

Pour faire simple, tu ne laisses pas de trou au milieu.
Le complémentaire des 3 cercles n'est pas composé de deux régions séparées.
Pour l'autre notion le wiki en anglais est le mieux:
winding number
L'indice d'un point par rapport à un polygone est facile à calculer de sorte qu'on peut savoir par un calcul si un point est intérieur à un polygone ou non.
Voici une autre référence définitive sur le sujet:
winding number pour les polygones

[Zavonen]

Sinon je vois plus ou moins ce que tu veux faire et ton idée me plait bien, de mon coté je planchais sur quelque chose pour trouver le nombre minimal théorique de cercles de mêmes rayons. J'expose ce que je pense : rapport de l'aire de la surface sur aire d'un cercle de rayon R donné donne un nombre qui si on prend sa partie entière et ajoute 1 donne un nombre minimal de disques. On n'ajouterai pas 1 si le quotient est déjà un entier ... Vous en pensez quoi ?

C'est naturel, mais cela risque de ne pas suffire.
Regarde déjà la perte par recouvrement dans le cas de 3 cercles recouvrant un triangle. Si la figure est grande et que le cercle est petit par rapport à elle, la perte globale sera nettement supérieure à un cercle.

[alphattm]

c'est ce à quoi je pensais par "plus ou moi quelque chose" ^^ merci en tout cas je creuse ( ou essaie ) je posterai les résultats quand j'en aurai

[alphattm]

Messieurs ..... rebonjour ^^

Bon je vous expose où j'en suis. Plutôt que de bloquer sur ce problème du nombre minimal de cercles je me suis dis :"Créons plusieurs méthodes de recouvrement de surfaces et comparons les".

C'est donc ce que j'ai commencé à faire.
COnsidérons que la surface soit un carré. Je me place en son centre que je prends comme centre d'un repère orthonormal. Bien.

Je trace mon premier cercle de rayon R. ( je suppose mes cercles de rayons constant dans toute cette partie ).
L'idée est d'utiliser des points connus comme point d'intersection. Ce premier cercle est le Cercle0.

Je trace un deuxième cercle qui coupe le cercle0 dont le centre est à une distance R'' pour l'instant quelconque du cercle0, ce sera le cercle1. Son centre a pour coordonnées (a,b)

Je calcule les 2 coordonnées des deux points d'intersections, j'en choisis un arbitrairement et à partir de lui je construits le 3e cercle ( Cercle2 [ comme 2e cercle de la 1ere couronne ndlr ] ).

On trouve son centre car on sait qu'il est à une distance R du point d'intersection entre les cercles0 et 1 et à une distance R'' du centre du cercle0 c'est à dite du centre du repère.

J'ai mon 3e cercle.
L'idée est de reproduire ça pour construire presque toute la 1ere couronne, je dois réfléchir à comment placer le dernier cercle qui sera surement un peu décaler et pour les couronnes suivantes avec des raisonnements analogues ça roule.



LE PROBLEME QUI SE POSE EST ALORS :
peut-on trouver un minimum à la somme de l'intersection de mes 3 cercles deux à deux entre eux?

J'utilise mathématica, je programme mon grigri, au final tout dépend de (a,b). Chouette ça, une fonction (moche,très moche) de deux variables !
Je trace ma somme des deux aires et la OH GRAND MALHEUR !!!!

J'obtiens un graphique avec des cercles concentriques que je n'arrive pas du tout à exploiter. Si quelqu'un pouvait m'aider à comprendre ....

NB:j'ai utilisé la fonction "ContourPlot" pour ceux qui connaissent mathématica en faisant varier a et b de -3 à 3.

lien vers mon graphe :

[alphattm]

merci aux courageux qui me liront, si besoin je vous posterai la construction !

[Maks]

Salut ! J'ai un doute sur la manière dont tu traces ton troisième cercle. J'ai compris que les cercles ont tous un rayon de R. Est-ce que, par hasard, tu aurais fixé la distance R'' ? Si oui, je crois avoir compris ta méthode.

Pour résumer :

Tu prends un cercle de rayon R et de centre O, et tu l'entoures de cercles de rayons R, dont les centres sont à une distance R'' de O. Et donc tu obtiens, comme tu le dis, une sorte de couronne de cercles. Est-ce bien là ta méthode ? (je préfère vérifier)

[alphattm]

TOUT A FAIT !!! youpi quelqu'un a réussi à comprendre mon bidule truc muche, c'est ça.

[Maks]

Ok, parfait, on va pouvoir commencer :ptdr:

En fait, je n'ai pas bien compris ce que tu as tracé. J'ai compris que tu avais representé le graphe d'une certaine fonction, des deux variables a et b. C'est la fonction en elle-même que je n'ai pas compris. Pourrais-tu ré-expliquer s'il te plaît ?

Sinon, une autre question qui me taraude : tu dis qu'il est facile de faire d'autres couronnes, mais cela ne me paraît pas si évident. En effet, pour faire la première couronne, on entour UN cercle, pas de problème, la démarche que tu proposes convient (sauf pour le dernier cercle, comme tu l'as justement dit, où il faut bricoler un peu). Mais pour faire une deuxième couronne ... Je ne vois pas comment ré-appliquer le même principe :mur:

[alphattm]

En fait le principe de ma construction c'est de dire, "tel point doit forcément être un point d'intersection de cercles" Une fois la première couronne construite les autres s'en déduisent un peu. Je fais un dessin et je l'up comme ça tu comprendras je fais ça après manger.

Ensuite ma fonction représente l'aire de la somme des intersections entre les cercles :
-0 et 1
-1 et 2
-2 et 0
ce que je ne comprends pas c'est l'analyse du graphe obtenu, a et b sont en abscisse et ordonné ? le disque représente toutes les valeurs prises ? Donc si c'est le cas mon intuition est la bonne, il existe un minimum ?

NB construction 2e couronne : grosso modo à partir des deux cercles de la première couronne que l'on a construit on déduit un premier cercle de la deuxième couronne et si on construit toute la première on peut en déduire une grosse partie de la 2e couronne ...