Plus courte ligne dans un carré <math xmlns='http://www.w3.org/1998/Math/MathML'><mn>10</mn><mo>×</mo><mn>10</mn></math>

1. Enoncé

Voici un problème provenant du passionnant site Diophante et proposé par Michel Lafond.

Dans un carré de 10 cm x 10 cm, tracer une ligne continue L = A ... B de longueur minimale, telle qu'aucun point du carré ne soit à plus d'un centimètre de L. Une façon moins formelle de présenter le problème pourrait être : un robot doit trouver toute trace de métal dans un carré de 10 mètres de côté à l'aide de son détecteur embarqué d'une portée de 1 mètre. Afin d'éconimiser l'énergie, on cherche à définir le chemin le plus court possible. Philippe Fondanaiche, responsable du site Diophante m'a assuré qu'il existe une solution de longueur inférieure à 54.47 cm. Pour faciliter les recherches, vous pouvez consulter la page de test.

2. Proposition

2.1. Spirale épineuse

On peut essayer une spirale en jouant sur l'écart entre les traits et en pauﬁnant pour les angles. Par exemple la ligne suivante a une longueur de 49 cm, mais elle ne répond pas à l'énoncé puisqu'il existe des régions où les points sont à plus d'un cm du trait le plus proche.

Dans cette ﬁgure on a agrandi la partie inférieure gauche et marqué en vert les régions où les points respectent l'énoncé. Il reste juste de toutes petites zones en forme de deltaplane qu'il nous faut recouvrir. Pour cela, il suﬃrait de passer par un point situé à 1 cm de la pointe du deltaplane.

Nous allons donc ajouter un aller retour en diagonale de

2 (1 - \sqrt{2}) \approx 0.8284

cm.

Le tout dernier trait utilise le même procédé, mais évite un aller-retour pour gagner sur la longueur. Au final, on aura une ligne de longueur totale :

49 + 17 (\sqrt{2} - 1) + 2 - \sqrt{2} = 34 + 16 \sqrt{2} \approx

56.6274 cm.

Il faut noter que si la ligne n'était pas nécessairement continue, nous n'aurions pas à doubler la longueur des pointes dans les coins de la spirale et nous obtiendrions alors une longueur de :

49 + 9 (\sqrt{2} - 1) + 2 - \sqrt{2} = 42 + 8 \sqrt{2} \approx

53.3137 cm.

2.2. Serpentin piquant

Nous allons chercher une forme de base plus courte. Le « radiateur » à gauche mesure 50 cm ce qui est plus long que la spirale, mais en contrepartie, il nécessite une pointe de moins. La longueur de la courbe, dans ce cas, est :

50 + 16 (\sqrt{2} - 1) = 34 + 16 \sqrt{2} \approx

56.6274 cm.

On obtient exactement la même longueur, mais on peut optimiser les allers-retours des pointes en en reliant les bouts comme dans le dessin ci-contre dont la longueur tombe alors à 55.66 cm.

Pour voir s'il est possible de faire mieux, nous allons tenter de déplacer les pointes et calculer la longueur résultante. Vous pouvez vous faire une idée de ce déplacement dans l'animation ci-contre. Calculons la longueur de la ligne en fonction de l'angle que fait le segment allant du centre du cercle vert à la pointe.

f (α) = 2 - x_{α} + \sqrt{(x_{α} - 1)^{2} + (y_{α} - 1)^{2}}

Et puisque le point variable décrit un cercle de rayon unité, on a :

x_{α} = cos α

x_{α} = sin α

. Il vient donc :

f (α) = 2 - cos (α) + \sqrt{3 - 2 (cos (α) + sin (α))}

Nous procédons par dichotomie pour trouver le meilleur angle grâce à un petit programme en Python. [voir le code source]

import math

def g(a):
  S = math.sin(a)
  C = math.cos(a)
  return 2 - C + math.sqrt(3 - 2*(C + S))  

def f(a):
  S = math.sin(a)
  C = math.cos(a)
  return S - (C - S)/math.sqrt(3-2*(C + S))
  
def findZero(precision):
  a = 0
  b = math.pi/2
  fa = f(a)
  fb = f(b)
  while fb - fa > precision:
    c = (a + b)/2.0
    fc = f(c)
    if fc < 0:
      a = c
      fa = fc
    else:
      b = c
      fb = fc
  return (a + b)/2
 
zero = findZero(0.000000001)
a = 1 - math.cos(zero)
b = 1 - math.sin(zero)
print "a = %.9f" %(a)
print "b = %.9f" %(b)

Et cela nous amène à une longueur de moins de 54.79 cm.

Mais il est encore possible d'améliorer la situation en remarquant que les segments horizontaux (qui relient des pointent) recouvrent une zone de 2cm d'épaisseur et que cela nous permet de déplacer les coins à la base des pointes comme le montre l'illustration à droite.

On passe alors à une longueur inférieure à 54.61 cm. Pour aﬃner encore un peu, il faut regarder les extrémités de notre courbe. Peut-être que le dernier segment serait plus court s'il n'était pas horizontal.

Voici les diﬀérentes mesures des segments rouges sur le schema de droite. Les valeurs de

H A

H C

sont déduites de la valeur de l'angle optimal des pointes calculé plus haut par dichotomie :

$A B = 2$
$A C = 1$
$H A \approx 0.826943425$
$H B = A B - H A \approx 1.173056575$
$H C \approx 0.562285134$
$B C = \sqrt{H C^{2} + H B^{2}} \approx 1.300855988$

Actuellement, le dernier segment de notre ligne a une longueur de

(0.346113151; 0)

. En le déplaçant dans l'axe

B C

, il devient

(\frac{H B * (B C - 1)}{B C}; \frac{H C * (B C - 1)}{B C}) \approx (0.271299128; 0.130042719) \approx 0.300855988

. On arrive alors à une longueur inférieure à 54.52 cm.

Il est peut-être possible d'aller plus loin puisque nous avons optimisé les deux derniers segments de notre ligne l'un après l'autre. Que se passe-t-il si nous tentons une optimisation simultanée. On a vu qu'une fois l'avant dernier point placé (le point

C

), il suﬃt que le dernier segment soit aligné sur

(B C)

pour qu'il soit le plus court possible. Sa longueur dépend biensûr de la position du point

C

qui se déplace sur un cercle de rayon unité centré en

A

Point	abscisse	ordonnée
$A$	$0$	$0$
$B$	$2$	$0$
$C$	$cos (α)$	$sin (α)$
$D$	$1$	$sin (α) + 1$
$H$	$cos (α)$	$0$

Voici les coordonnées des diﬀérents points en fonction de l'angle

α

(l'axe des ordonnées est dirigé vers le bas). L'ordonnée de

D

vaut au maximum 2. Pour calculer la longeur des deux derniers segments, il ne faut pas oublier d'ajouter une partie verticale qui descent sous

D

. Nous l'arrêterons à l'ordonnée 2.

Ainsi la longeur (en fonction de

α

) est composée de trois sections :

le dernier segment de longueur $C B - 1$ ,
le segment CD et
la partie verticale de longueur $2 - D_{y}$ .

On obtient la fonction

f (α) = \sqrt{5 - 4 cos (α)} + \sqrt{{cos}^{2} (α) - 2 cos (α) + 2} - sin (α)

, de dérivée

f' (α) = \frac{2 sin (α)}{\sqrt{5 - 4 cos (α)}} + \frac{sin (α) (1 - cos (α))}{\sqrt{{cos}^{2} (α) - 2 cos (α) + 2}} - cos (α)

Une nouvelle dichotomie nous donne la valeur de

α \approx 0.519402354

. On a encore gagné un dixième de milimètre : 54.51 cm. On constate que le segment

[C D]

n'est plus parallèle à

[K L]

. On peut donc essayer de déplacer le point

K

pour tenter de raccourcir encore le parcours. On est soumis aux contraintes suivantes :

Point	abscisse	ordonnée
$B$	$2$	$0$
$K$	$2 + cos (α)$	$sin (α)$
$L$	$3$	$L_{y} (α)$
$M$	$5.173056575$	$0.562285134$
$N$	$5$	$1.562285134$

les points $M$ et $N$ sont ﬁxes,
l'ordonnées de $L$ est variable, mais sont abscisse doit rester égale à $3$ ,
la distance entre $L$ et la droite $(K M)$ doit être de 1 cm,
$[K L]$ ne doit pas être trop verticale pour ne pas perdre en recouvrement.

Pour calculer

L_{y} (α)

, il faut trouver la distance de

L

à la droite

(M K)

d'équation

a x + b y + c = 0

et dire qu'elle vaut 1 cm. Il faut donc résoudre :

\sqrt{a^{2} + b^{2}} = | 3 a + L_{y} b + c |

Puisque la droite

(K M)

ne peut pas être verticale, on peut se ramener à une équation simpliﬁée

y = a x + c

en posant

b = - 1

. Ainsi, il suﬃt maintenant de résoudre :

\sqrt{a^{2} + 1} = | 3 a - L_{y} + c | a = \frac{K_{y} - M_{y}}{K_{x} - M_{x}} c = M_{y} - M_{x} \frac{K_{y} - M_{y}}{K_{x} - M_{x}}

Une étude graphique montre que la longueur est minimale quand

α

vaut approximativement

0.674644046

radians. Encore une fois, c'est un programme Python qui nous es venu en aide. [Code source]

import math

Mx = 5.173056575
My = 0.562285134

def f(alpha, precision):
  S = math.sin(alpha)
  C = math.cos(alpha)
  Kx = 2.0 + C
  Ky = S
  a = (Ky - My)/(Kx - Mx)
  aa = math.sqrt(a*a + 1.0)
  c = My - Mx*a
  Lmin = 0.0
  Lmax = 3.0
  valLmin = abs(3*a - Lmin + c) - aa
  valLmax = abs(3*a - Lmax + c) - aa
  if valLmin > valLmax:
    valLmoy = valLmin
    valLmin = valLmax
    valLmax = valLmoy
  while valLmax - valLmin > precision:  
    Lmoy = (Lmin + Lmax)/2    
    valLmoy = abs(3*a - Lmoy + c) - aa
    if valLmoy < 0:
      Lmin = Lmoy
      valLmin = valLmoy
    else:
      Lmax = Lmoy
      valLmax = valLmoy
  Ly = (Lmax + Lmin)/2
  length = math.sqrt((Mx - Kx)**2 + (My - Ky)**2) + math.sqrt((Kx - 3)**2 + (Ky - Ly)**2) - Ly
  return (Ly, length)
  
min = 0
max = math.pi/2
steps = 1000
step = 0
zx = 1
lengthMin = 10.5
lengthMax = 2.7
alphaMin = 0
zy = 1000/(lengthMax - lengthMin)
while step < steps:
  alpha = min + ((max - min)*step)/steps
  (Ly, length) = f(alpha, 0.000000001)
  if length > lengthMax: lengthMax = length
  if length < lengthMin:
    lengthMin = length
    alphaMin = alpha
    x = step*zx
    y = 1000 - (length - lengthMin)*zy
    print "L%.3f,%.3f" %(x, y),
    if step %5 == 0:
      print
  step = step + 1

print
print "alpha = %.9f, length = %.9f" %(alphaMin, lengthMin)
print "x = %.3f" %((1000.0*alphaMin)/(math.pi/2.0))

On en déduit donc que

K = (2.780929354, 0.624619359)

L = (3, 1.619250313)

. Et on tombe alors à 54.49 cm.

Il suﬃt alors de généraliser cette dernière optimisation à toutes les pointes et on obtient alors une longueur égale à 54.44180 inférieure à : 54.45 cm. Nous nous arrêtons là faute d'idée nouvelle, mais il est probable qu'on puisse encore faire mieux. En eﬀet, nos optimisations n'ont jamais été globales à la ligne entière : on a toujours optimisé en ﬁxant des points que l'on a fait varier dans une seconde étape.