Recouvrement "minimal" d'une surface

par **alphattm** » 17 Juil 2009, 18:03

ok le dessin est moche mais ça aide à comprendre le cercle 3 appartient à la 2e couronne

par **Maks** » 17 Juil 2009, 18:08

Ah d'accord, j'ai compris ta fonction. Cependant, vu l'approche que nous avons du problème, je pense qu'il serait préférable de regarder, dans un premier temps, ce qu'il se passe avec une seule couronne. Il faut déjà voir si nous arrivons à résoudre ce cas. Que trouves-tu comme fonction ? (explique ta démarche pour la trouver) Par contre, je ne vois pas du tout pourquoi tu utilises a et b comme variable en fait. Déplacer le cercle initial ne change en rien la disposition des cercles, et donc pas l'aire des intersections ! Je pense qu'il ne faut prendre comme variable que R et R''. En fait, on part plus sur le problème "comment minimiser les pertes ?" que sur le problème "comment recouvrir un carré ?". Mais je pense que c'est une première étape.

par **Maks** » 17 Juil 2009, 18:52

En fait, je pense qu'il faut déjà régler le problème du dernier cercle. Je ne vois même pas comment tu as traité la chose sans plus de détails en fait ...
Voila une figure que j'ai realisé, avec R=1.5 et R''=2.5. Comment ferais-tu pour mettre le dernier cercle ? On a bien sûr envie de mettre son centre au milieu du petit segment vide, mais bon ... Le mieux serait de calculer le rapport R/R'' pour que ça tombe juste ! Qu'en penses-tu ?

par **alphattm** » 17 Juil 2009, 19:00

je crois qu'il y a erreur sur a et b. Je rappelle que ce sont les coordonnées du centre du cercle 1, je maintiens donc que les coordonnées de a et b desquels on déduit celles du centre du cercle 2 ont un impact sur les aires puisque toutes les longueurs et constructions sont calculées / faites grâce à celles ci.

Le problème est bien de chercher à optimiser les aires d'intersection. J'ai pris volontairement un problème symétrique dans un premier temps pour faciliter les choses qui sont pas très évidentes. Bien évidemment on arrivera à recouvrir la surface mais ce que je cherche à faire c'est d'y mettre le moins de cercle possible et d'où l'idée de minimiser les surfaces d'intersections de mes cercles.

J'ajouterai que comme on a placé l'origine du repère sur le centre du cercle 0, R" est connu grâce à a et b. R" = Racine ( a²+b² )

Revenons sur l'obtention de cette fonction. Comme expliqué précédemment je place arbitrairement le cercle 1, grâce auquel je construis mon cercle 2. Les coordonnées du centre du cercle 2 dépendent expressément de celles du cercle 1 ainsi que de R, je n'irai pas jusqu'à copier le résultat que j'ai obtenu qui est horrible mais ça semble logique puisque le centre est obtenu par l'intersection de deux arc de cercles : celui de centre le centre du cercle0 et de rayon R" et celui de centre un point d'intersection entre les cercles 0 et 1 ( celui d'où part le trait vert clair sur ma figure ) et de rayon R.

A partir de là je calcule les 3 aires de surfaces communes des 3 cercles ( 0 et 1, 0 et 2 , 1 et 2 )
Ces aires dépendent de a, b et R.

Puis je fixe R=1 arbitrairement et je trace la fonction f(a,b) qui donne comme résultat la somme des surfaces communes, c'est à dire "la surface commune totale" comprendre intersection de deux cercles. Et j'obtiens cette espèce de fonction bizarre mais peut être pas temps que ça !

Ais je répondu à ta question ? ( j'ai bien conscience d'être cafouilleux dans mes explications )

(((
NB : j'ai essayé à la main d'appliquer ma méthode sur un carré, je trouve 29 cercles avec je pense une possibilité d'optimisation. De plus en changeant de méthode je n'en trouve alors que 25.
)))

par **alphattm** » 17 Juil 2009, 19:10

oups mon post arrive trop tard. Pour répondre au tient, je n'avais pas particulièrement pensé au rapport R/R' d'ailleurs je ne comprends pas trop son utilité.

Concernant ce dernier cercle, l'envie que j'ai c'est d'étudier la fonction qui donnerait la surface commune avec les cercles que ce dernier coupe à savoir 0, 1 et (n-1) de la même façon, en fonction des coordonnées du centre.
Je placerai donc ce cercle en fonction du résultat le plus favorable.

Sinon je m'étais dis aussi qu'on pourrait faire que ça tombe "juste" mais je tenais à voir le cas "optimal", est ce que par hasard ça ne serait pas déjà un cas "tout bon", """comme par hasard""".

Sinon je pensais au racines de l'unité ..... mes centres des cercles pourraient être des racines de l'unité pour obtenir une première couronne parfaite. Dans ce cas la pas de soucis du dernier cercle.

Rapport R'/R ....... ça me donne une idée ça. On est d'accord que plus le cercle est gros moins il y en a. Une fonction de 3 variables ça existe ? :we: ça permettrait d'enlever l'hypothèse R = 1 .....

Edit hors sujet : je vais fouiller dans mes DM on sait jamais ... j'ai peut être un résultat intéressant

par **Maks** » 17 Juil 2009, 19:52

Au temps pour moi pour a et b, je n'avais pas fait attention :marteau:

Donc si j'ai bien saisi, le graphe de f que tu me présentes ne concerne que trois cercles ? La "symétrie circulaire" du graphe est rassurante, et normale. Par contre, il serait intéressant de superposer à ce graphe le cercle initial (de rayon 1, si j'ai bien compris), on y verrait un peu plus clair, et d'expliquer les couleurs.

Sinon, je parlais du rapport R/R' pour faire en sorte que le dernier cercle tombe juste. Cela me paraît logique car si tu as une figure où le dernier cercle tombe juste, en faisant une homothétie de centre 0 et de rapport quelconque, alors le dernier cercle (transformé par l'homothétie) tombe encore juste sur la nouvelle figure. Par contre, s'il ne tombe pas juste, alors il ne tombera toujours pas juste avec une homothétie. C'est dur à expliquer je trouve. Je ne sais pas si tu comprends mon raisonnement. Au final, j'en déduis qu'il doit exister une condition sur le rapport R/R' pour que le dernier cercle tombe juste. Enfin tout cela n'est qu'intuitif et mériterait bien sûr des démonstrations rigoureuses, si l'on veut faire les choses bien.

Concernant ton idée de fonction pour placer le dernier cercle, je me demande si elle ne serait pas constante. En effet, déplacer un peu le rayon sur le cercle rouge (cf ma figure) "enleverait" de l'aire d'un côté (disons du côté du cercle 1), et en rajouterait de l'autre (du côté du cercle n-1 donc), et j'ai bien l'impression que ça se compense. Je ne parle bien sûr pas de l'intersection avec le cercle 0 car il est évident que l'aire qui lui correspond est constante quand le centre se déplace sur la ligne rouge.
Suis-je clair ? :marteau:

Tout cela est très interessant en tout cas.

par **emdro** » 17 Juil 2009, 20:53

Bonsoir,

quelques références:
ici et là.

Bon courage...

par **Maks** » 17 Juil 2009, 20:57

Ah super ! Je lirai tout ça demain. Bonne nuit à toi, et merci encore !

par **alphattm** » 17 Juil 2009, 21:03

idem je lirai ça.

Il parait que la nuit porte conseil ^^ je vais méditer tout ça

je ne sais pas à quoi correspondent les couleurs sur le graphe :D je dois le bosser

ok j'ai compris ton idée avec l'homothétie qui rejoint la mienne en fait : les centres des cercles reliés forment un polygone régulier, c'est à dire les centres sont des racines n-ième de l'unité mais il faut alors supposer le rayon R"=1

par **alphattm** » 18 Juil 2009, 08:41

ces deux cas (liens donnés) sont intéressant :
http://www.diophante.fr/D4.-Pavage-du-plan-et-de-l-espace-Dissection/D402.-Comment-recouvrir-une-table-carree-avec-des-napperons-circulaires.html

http://www.diophante.fr/D4.-Pavage-du-plan-et-de-l-espace-Dissection/D410.-Le-recouvrement-du-triangle-equilateral-par-des-cercles.html

par **alphattm** » 18 Juil 2009, 09:01

RECTIFICATION : j'utilisai une mauvaise fonction (ContourPlot), je l'ai retracé avec Plot3D et c'est beaucoup plus lisible !!!!

La voici :

NB : je viens de lancer la résolution de l'annulation des dérivées partielles mais j'ai l'impression que ça va prendre du temps :O

par **Maks** » 18 Juil 2009, 17:15

Il faudrait une autre vue. Par contre, je comprends pas trop pourquoi f augmente quand on s'écarte de 0. J'aurais plutôt dit le contraire. Je vais essayer avec d'autres figures, pour voir un peu si je me plante.

par **Maks** » 18 Juil 2009, 19:05

Voilà trois schémas, à R fixé, où j'ai fait varié R'. Il semble que pour R' proche de R, l'aire soit très grande. De plus, il semble que l'aire soit maximale quand R' vaut 0 (air totale d'un disque). Ca ne colle pas beaucoup avec ton graphique. On devrait en effet voir un pic à l'origine. Non ? Je vais essayer de trouver la fonction, et nous comparerons.

PS : ne pas tenir compte du cercle rouge. Il m'a servi pour la construction, et a pour rayon R'.

par **alphattm** » 18 Juil 2009, 19:27

il y a en effet un petit pic sur le graphique au alentours de 0 que l'on ne voit pas sur la figure. Je vais vérifier mes calculs dans ce cas

par **Maks** » 18 Juil 2009, 19:45

Au fait, que fais-tu quand il y a une zone où les trois cercles se superposent ? Tu comptes l'aire une fois ou trois fois ? (cf la zone centrale de mon dernier schéma)

par **alphattm** » 18 Juil 2009, 20:54

et bien en fait je pensais avoir conçu mon algorithme de construction de telle sorte que cela n'arrive jamais ..... xD il faut donc que je rajoute une condition sur R et R' ... oulala mon sujet commence à m'échapper ^^

par **Maks** » 18 Juil 2009, 20:58

Non, non, c'est bien. C'est ça aussi la recherche. Je vais essayer de mon côté aussi. En tout cas, je pense qu'il est important qu'on se concentre d'abord sur le cas de 3 cercles. Bon, j'y vais. A demain.

par **alphattm** » 18 Juil 2009, 21:00

idem à demain !! ^^

par **alphattm** » 19 Juil 2009, 08:21

bon alors, je suis en train de modif mon algo, tu avais raison on peut et même on doit prendre R et R' comme paramètres. Pour simplifier les calcul autant prendre le centre du premier cercle avec pour coordonnées (a,0) d'où R'=a, ceci libère la variable b et on peut ainsi éventuellement faire une étude en faisant varier R et R' en même temps.

Je suis en train de modifier ceci

par **alphattm** » 19 Juil 2009, 08:37

flute j'obtiens quelque chose qui donne une aire négative. Sinon les aires sont comptés plusieurs fois. Si je veux couvrir mon carré avec le moins de cercle il faut dévaloriser les zones où les 3 cercles se coupent.

Recouvrement "minimal" d'une surface

Qui est en ligne