Inscription / Connexion Nouveau Sujet
Frontière minimale
Bonjour à tous 
Un pendant rectiligne au problème 
Un ballon dans les clous que l'on peut traiter indépendamment du précédent . En tout cas il met de côté tous les problèmes d'arrondis . Est-il beaucoup plus facile pour autant ?
La figure ci-dessous est très particulière :
1°) Elle est d'intérieur connexe .
2°) Sa frontière est constituée de segments parallèles aux axes de coordonnées d'un quadrillage orthonormé et dont les sommets sont à coordonnées entières .
3°) Tout point à coordonnées entières de son enveloppe convexe est sur sa frontière .
La question :
Quelle est la longueur minimale de la frontière de la figure si son aire est donnée ?
Pour la figure proposée l'aire est de 28 pour une longueur de 50 , on est bien loin du minimum .
On s'amuse sans blanker .
Imod
Je viens de me rendre compte que la formulation du 3°) point n'est pas correcte . Il s'agit des points à l'intérieur du lacet enfermant la figure .
Imod
(re)bonjour,
Pas sûr que ce soit mieux, parce que les points sur la frontière des trous aussi.
mais ce point 3 est il nécessaire / utile ?
à partir du moment ou tous les segments sont à extrémités des points de la grille et parallèles aux axes, cela suffit (avec la connexité)
si les seuls points communs possibles entre deux segments, s'ils en ont, sont uniquement leurs extrémités.
ah ça y est je viens de comprendre ce que tu voulais dire par ce point 3
tu exclus des zones plus larges que 1 :
est exclue.
bref point 3 : aucun point à coordonnée entières dans son intérieur
(ni dans l'intérieur des trous ?)
Oui , mais je ne trouve pas de formulation simple du 3°)
Je parlais d'enveloppe convexe pour distinguer l'intérieur au sens topologique de l'intérieur au sens commun : les trous sont à l'intérieur de la figure mais ne font pas parti de son intérieur . Malheureusement cette façon de présenter les choses ne marche pas . Je suis complètement ouvert à toute formulation plus simple
Imod
l'intérieur de la surface c'est ce qui est peint en vert
donc il suffit de dire "aucun point entier à l'intérieur de la surface"
en ayant ainsi désormais précisé, au cas où quelqu'un interprèterait comme "l'intérieur de la figure" 
le problème des polygones à trou n'est pas simple
déja avec Geogebra il faut jongler pour le tracer / le peindre :
avec l'outils "polygone" c'est impossible : il rejette les points cliqués en double
il faut le faire en ligne de commande :
Polygone(A, B, C, D, E, F, G, H, E, D, A)
et masquer les deux arêtes DE et ED
ou alors le tracer comme l'union de deux (ou plus) polygones, et masquer les (au moins) quatre arêtes en trop
.
une remarque aussi : on peut interdire aussi les points entiers à l'intérieur des trous qui ne seraient pas sur leur pourtour, ça ne va pas trop perturber ...
et du coup, qu'on dise l'intérieur de la surface ou l'intérieur de la figure c'est pareil.
Bonsoir,
pour le 3) je dirais qu'il n'y a pas de point à coordonnées entières à l'intérieur de la zone.
Quelques réflexions sur le sujet.
Toutes les « chenilles » 
d'aire a ont une frontière de longueur 2a+2. Pour a<8 on ne peut pas faire mieux.
Pour a=8 on peut faire mieux 
et la longueur maximale de la frontière est inférieure ou égale à 2a pour tous les nombres pairs supérieurs à 8 : on fait un anneau 
.
Je ne peux plus mettre d'images mais il est évident que l'on va avoir quelque chose de compliqué.
Pour une aire de 28 j'ai l'impression que la frontière minimale est 48.
Je crois que j'ai trouvé une formulation du 3°) correcte et compréhensible :
3°) Tous les points à coordonnées entières dans l'enveloppe de la figure sont sur sa frontière .
Je sais bien que le terme "enveloppe" ne veut pas dire grand chose mais faute de grives...
Imod
Plutôt "cernés" par l'enveloppe de la figure .
J'aurais dû réfléchir un peu plus avant de lancer le sujet qui va devenir assez difficile à suivre 
Bienvenu à Verdurin au passage
Imod
je suis du même avis pour aire = 28
il y a aussi des équivalences entre des figures de même aire et même longueur de frontière.
on peut alors chercher à minimiser l'aire des trous ...
et puis on peut aussi se poser la question des points doubles sur la frontière :
il n'y a pas de segment BE là dedans
la frontière c'est G-A-B puis plus loin D-A-E
et pareil pour les points doubles sur la frontière externe.
ils n'en posent pas si on précise bien où passe la frontière en ces points doubles.
je ne disais que ça.
la longueur non , mais la notion d'intérieur et d'extérieur avec des segments qui se croisent est juste "plus délicate"
enfin, bon, tu as raison tout de même
l'intérieur de ça c'est bien ce qui est peint :
et pas ce qui est "à main droite en tournant le long du pourtour"
(ou à main gauche si on tourne dans l'autre sens)
Pour continuer on va avoir des choses comme ça : 
Ce qui permet d'avoir une idée du rapport aire/frontière quand l'aire tend vers l'infini.
oui, si on augmente l'aire on est amené à la remplir de trous pour garantir qu'il n'y a pas de points entiers dans l'intérieur....
ces structures carrées font partie de ce qu'il est aisé de calculer en fonction du côté (ou du nombre de trous)
ne serait-ce pas une branche parabolique ?
ou alors le rapport aire/frontière² ?
En effet la disposition en carré avec des petits trous carrés de côté 1 est la plus performante . La même disposition peut être utilisée avec des rectangles à côtés impairs 2a+1 et 2b+1 . L'aire colorée vaut alors 3ab+2a+2b+1 et la frontière 4(ab+a+b+1) . Après pour une aire donnée il peut ne pas y avoir de décomposition n=3ab+2a+2b+1 ou plusieurs et alors le choix de la configuration la plus performante n'est pas évident du tout .
Imod
En recyclant ce que j'avais fait pour les bulles et en mettant juste longueur d'un arc = 1 et aire d'un arc = 0 :
pour les configurations de cette liste là ( c=nombre de carrés = aire et a = nombre d'arètes = périmètre)
en en ajoutant à chaque tapis à trou une "queue" de 1 à 5 carrés,
on obtient les meilleures configurations jusqu'à une aire de 42
ensuite les variantes incomplètes du tapis de (2n+1)² sont trop nombreuses pour les lister à la main.
en vert les chaines linéaires
en rouge les tapis de la figure d'avant
en rouge entourés les tapis (2k+1)²
en bleu les queues linéaires accrochées dessus
PS : sachant qu'il y a de nombreuses configurations qui sont "équivalentes" (exactement même aire et même périmètre avec une forme différente)
En fait l'évolution de la figure n'est pas vraiment chaotique , on reste autour du carré troué plus ou moins déformé . Plus on agrandit l'aire de la figure et plus on s'approche du rapport A/L=3/4 avec une figure proche d'un carré et très peu de perturbations .
Imod
Annuler
connectez vous