Final Report: Motion of Objects in Contact (Hopcroft & Wilfong)

Rapport: Mouvement d’Objets en Contact

Younesse Kaddar

Article étudié: Motion of Objects in Contact (J. Hopcroft & G. Wilfong, 1986)

Version PDF|Slides|Rapport en ligne

  • |-|-
\newcommand{\int}{\mathop{\rm int}\nolimits} \newcommand{\cl}{\mathop{\rm cl}\nolimits} \newcommand{\bu}{\bullet} \newcommand{\INT}{\mathop{\bf INTERSECT}\nolimits} \newcommand{\INTp}{\mathop{\bf INTERSECT'}\nolimits} \newcommand{\FILL}{\mathop{\bf FILL}\nolimits} \newcommand{\OVER}{\mathop{\bf OVERLAP}\nolimits} \newcommand{\OVERp}{\mathop{\bf OVERLAP'}\nolimits} \newcommand{\BASE}{\mathop{\bf BASE}\nolimits} \newcommand{\NON}{\mathop{\bf NONOVERLAP}\nolimits} \newcommand{\VALID}{\mathop{\bf VALID}\nolimits} \newcommand{\TOUCH}{\mathop{\bf TOUCH}\nolimits} \newcommand{\Im}{\mathop{\rm Im}\nolimits}

Introduction

Cet article fondateur fait un premier pas pour poser les bases d’une théorie des transformations d’objets, en démontrant le théorème suivant d’existence de mouvement en contact:

Illustration du théorème

Théorème principal (Hopcroft & Wilfong):

S’il existe un mouvement de rotations et de translations entre deux configurations dans lesquelles un ensemble d’objets forment une composante connexe, alors il existe un mouvement entre ces deux configurations tel qu’à tout instant, les objets forment une composante connexe.

Ce que nous avons vu en cours sous la forme: “Dès qu’il y a un chemin dans l’espace libre, il y a un chemin au contact”.


De l’importance de la contractilité

Notons que si l’espace des configurations n’est pas contractile, le théorème ne s’applique pas (d’où le fait que nous autorisions des mouvements par translations), comme illustré par l’exemple suivant à un degré de liberté (l’espace des configurations est un cercle, en identifiant l’angle $2π-2θ$ et $2θ$):

Illustration du théorème Illustration du théorème

Le seul mouvement de l’angle $θ$ à l’angle $-θ$ ne garde pas la boule et la barre en contact.

Espace des configurations

Un objet est défini comme une partie convexe compacte de $ℝ^n$, égale à l’adhérence de son intérieur et bornée par un nombre fini de surfaces algébriques. La position et l’orientation de chaque objet est déterminée par une origine et un repère qui leur sont associés. Un objet composé est un objet constituté de plusieurs sous-objets, auquel on associe un graphe dont les sommets sont les objets et les arêtes lient deux sous-objets qui s’intersectent. Un des sous-objets est appelé la base: son origine est celle de l’objet composé. Tout objet peut être vu comme un objet composé à un seul sous-objet (sa base).

Une configuration est un vecteur de position et d’orientation des objets : ces vecteurs forment un espace de configuration. $B(x)$ (resp. $b(x)$) désignera la partie (resp. le point) de $ℝ^n$ occupé(e) par l’objet $B$ (resp. le point $b$) dans la configuration $x$.

Si $x$ est une configuration, on dit que deux objets $B_i, B_j$:

   
s’intersectent en $x$ si $B_i(x) ∩ B_j(x) ≠ ∅$
se chevauchent en $x$ si $\int(B_i(x)) ∩ \int(B_j(x)) ≠ ∅$
se touchent en $x$ si $B_i(x) ∩ B_j(x) ≠ ∅ ∧ \int(B_i(x)) ∩ \int(B_j(x)) = ∅$

On définit les ensembles de configurations suivants:

Ensemble Configurations $x$ en lesquelles
PROPER chaque objet composé a un graphe associé connexe (objets composés connexes et configurations propres)
VALID chaque objet composé est connexe et est tel que tous les sous-objets qui s’intersectent se touchent (configurations valides)
PROPER

Ensemble Configurations $x$ valides telles qu’il existe (au moins) deux objets
INTERSECT qui s’intersectent en $x$
OVERLAP qui se chevauchent en $x$
TOUCH qui se touchent en $x$
INTERSECT

Ensemble Configurations $x$ propres telles que
BASE la base d’un objet composé intersecte la base d’un autre (les bases sont indiquées en gras dans les schémas)
INTERSECT

Enfin, on pose \NON ≝ \VALID\backslash\OVER \\ \FILL ≝ \cl(\OVER) ∪ \BASE

Pourquoi avoir recours à $\FILL$?

Comme le montre l’exemple suivant, où $A_i$ est un objet composé de base $A_{i, 1}$ fixe et $B$ un objet (mobile), $\NON ∪ \cl(\OVER)$ n’est pas contractile en général (ce qui est un point clé de la preuve): en ajoutant $\BASE$ (qui n’est pas inclus dans $\VALID$) à $\cl(\OVER)$, on rend $\FILL ≝ \cl(\OVER) ∪ \BASE$ contractile (voir le gif animé ici).

INTERSECT

Détermination de TOUCH

Attention avec TOUCH

On pourrait penser que TOUCH est la frontière de INTERSECT, mais ce n’est pas le cas ! Considérer l’exemple suivant, avec deux objets $B_1$ et $B_2$ (voir le gif animé ici):

INTERSECT

Les configurations en lesquelles $B_1$ est dans le col de $B_2$ sont dans TOUCH mais pas dans la frontière de INTERSECT.


\TOUCH = \NON ∩ \cl(\OVER)

Esquisse de preuve: Comme les objets sont égaux à l’adhérence de leur intérieur (pour $⊆$) - de même que les objets composés, puisque $\cl(\int(\bu))$ préseve l’union finie - et compacts (pour $⊇$), on montre que \underbrace{\left\lbrace x \mid ∃i≠ j. \overbrace{A_i}^{\llap{\text{objet composé}}}(x) ∩ \overbrace{A_j}^{\rlap{\text{objet composé}}}(x) ≠ ∅ \right\rbrace}_{\text{noté } \INTp \not ⊆ \VALID} = \cl\Bigg(\underbrace{\left\lbrace x \mid ∃i≠ j. \int(A_i(x)) ∩ \int(A_j(x)) ≠ ∅ \right\rbrace}_{\text{noté } \OVERp \not ⊆ \VALID}\Bigg)

Par fermeture de $\VALID$, il vient alors

\cl\Big(\underbrace{\OVER}_{≝\, \OVERp ∩ \VALID}\Big) = \cl(\OVERp) ∩ \VALID

Et on conclut par \begin{align*} \TOUCH & = \OVERp^c ∩ \INTp ∩ \VALID\\ &= \OVERp^c ∩ \VALID ∩ \INTp ∩ \VALID\\ & = \underbrace{\OVERp^c ∩ \VALID}_{ = (\OVERp ∪ \VALID)^c ∩ \VALID \, =\, \NON} ∩ \cl(\OVER) \\ & = \NON ∩ \cl(\OVER) \end{align*}

Puis, comme $\BASE ∩ \NON ⊆ \TOUCH$:

\TOUCH = \FILL ∩ \cl(\OVER)

Connexité et contractilité

On montre le lemme suivant :

Si $A$ et $B$ sont des objets qui coïncident

  • en $A \ni a_1 = b_1 ∈ B$ dans la configuration $x$
  • en $A \ni a_2 = b_2 ∈ B$ dans la configuration $y$

alors il existe une translation de $A$ et $B$ entre $x$ et $y$ au cours de laquelle ils continuent de s’intersecter.

Preuve: On translate de telle sorte que le point $c_t = a_1 + (a_2-a_1)t = b_1 + (b_2-b_1)t$ reste un point d’intersection en $A$ et $B$ (voir le gif animé ici).

INTERSECT INTERSECT INTERSECT INTERSECT

Avec le lemme précédent et des mouvements de rotation, on démontre que

BASE et FILL sont connexes par arcs

ainsi que le lemme suivant :

Lemme : De toute configuration dans VALID (resp. BASE), il existe un chemin dans VALID (resp. BASE) vers une configuration dans BASE où les origines des objets composés coïncident.

pour enfin conclure que

Corollaire : \FILL ∪ \NON = \BASE ∪ \VALID est contractile (et donc connexe par arcs)

Mayer-Vietoris

Intuitivement:

  • l’homologie correspond à l’ensemble des invariants topologiques de $X$, indiqués par des groupes d’homologie
  • le $k$-ième groupe d’homologie $H_{k}(X)$ a autant de copies de $ℤ$ que $X$ contient de “trous” de dimension $k$. On utilisera donc le fait que :

    • $H_0(X) ≃ ℤ^m$ si et seulement si $X$ a $m$ composantes connexes
    • Si $X$ est contractile, alors $H_1(X) ≃ \lbrace 0 \rbrace$ (il ne peut pas y avoir de “trous”, par contractilité)

Mayer-Vietoris: La suite suivante est exacte:

\begin{align*} H_1(\FILL ∪ \NON) & {\xrightarrow {\partial _{*}}}\,H_0(\overbrace{\FILL ∩ \NON}^{=\, \TOUCH})\\ & {\xrightarrow {(i_{*},j_{*})}}\,H_0(\FILL)\oplus H_0(\NON) \\ & {\xrightarrow {k_{*}-l_{*}}}\,H_0(\FILL ∪ \NON) \\ & {\xrightarrow {\partial _{*}}}\, \lbrace 0 \rbrace \end{align*}

où $i, j, k, l$ sont les inclusions, et $\partial _{*}$ est défini à partir de l’opérateur bord.

Or, ici :

  • $H_1(\FILL ∪ \NON) = \lbrace 0 \rbrace$ par contractilité
  • $H_0(\FILL) = H_0(\FILL ∪ \NON) = ℤ$ par connexité par arcs

La suite suivante est donc une suite exacte courte :

\lbrace 0 \rbrace ⟶ \,H_0(\TOUCH) \,{\xrightarrow {(i_{*},j_{*})}} \, ℤ \oplus H_0(\NON) {\xrightarrow {k_{*}-l_{*}}}\, ℤ ⟶ \, \lbrace 0 \rbrace

Et par injectivité de $(i_{*},j_{*})$ et surjectivité de $k_{*}-l_{*}$:

\Big(ℤ\oplus H_0(\NON)\Big)/\underbrace{\Im (i_{*},j_{*})}_{≃ \,H_0(\TOUCH)} ≃ ℤ
⟹ H_0(\NON) ≃ H_0(\TOUCH)

C’est-à-dire que $\NON$ et $\TOUCH$ ont le même nombre de composantes connexes !

Puis, le principe des tiroirs nous permet de conclure, après avoir montré que chaque composante connexe de $\NON$ contient une et une seule composante connexe de $\TOUCH$. En effet:

  • chaque composante connexe $t$ de $\TOUCH$ intersecte au plus une composante connexe de $\NON$, car sinon, si deux composantes $n_1, n_2 ⊆ \NON$ étaient intersectées par $t$: tout $x_1 ∈ n_1$ serait relié à tout $x_2 ∈ n_2$ par un chemin continu allant de $x_1$ à $t_1 ∈ t ∩ n_1 ≠ ∅$ (par connexité de $n_1$), puis de $t_1$ à $t_2 ∈ t ∩ n_2 ≠ ∅$ (connexité de $t$), et enfin de $t_2$ à $x_2$ (connexité de $n_2$).

  • chaque composante connexe $n$ de $\NON$ contient au moins une composante connexe de $\TOUCH$, car en translatant linéairement l’origine d’un objet $A_1$ vers celle d’un objet $A_2$ (et en notant $m(t)$ cette translation), les objets se touchent à l’instant t_0 ≝ \min_t \Big\lbrace m(t) \mid \begin{align*} &\quad m(t) ∉ \NON \backslash \TOUCH\\ ⟺ &\quad m(t) ∈ \OVER ∪ \TOUCH \end{align*}\Big\rbrace

Conclusion

On a montré que si

  • il existe un chemin d’une configuration $x ∈ \TOUCH$ à $y ∈ \TOUCH$ dans $\NON$
  • i.e $x ∈ \TOUCH$ et $y ∈ \TOUCH$ appartiennent à la même composante connexe $n ⊆ \NON$

alors

  • en notant $t$ l’unique composante connexe de $\TOUCH$ qui intersecte $n$, nécessairement $x ∈ \TOUCH$ et $y ∈ \TOUCH$ appartiennent à $t$
  • i.e $x$ et $y$ appartiennent une même composante connexe $\TOUCH \supset t ⊆ n$
  • i.e. il existe un chemin de $x$ à $y$ dans $\TOUCH$

Enfin, on acquiert le résultat voulu en montrant, par induction sur le nombre $n$ d’objets composés, que : si il existe mouvement à $k+1$ composantes connexes (i.e à tout instant, il y a au plus $k+1$ composantes connexes) entre deux configuration à $k$ composantes connexes, alors il existe un mouvement à $k$ composantes connexes entre ces deux configurations (pour $1 ≤ k <n-1$).

Leave a comment