Régions déterminées par des droites d’un plan

Il existe une jolie relation permettant calculer le nombre de régions en lesquelles des droites d’un plan affine \mathcal{E} partagent celui-ci. Cette relation me pose par ailleurs un problème de nature algébrique dont je n’ai pas la solution et que vous aurez peut-être à coeur de résoudre.

Par définitions, les régions déterminées par des droites \mathcal{D}_1,...,\mathcal{D}_d de \mathcal{E} sont les composantes connexes du complémentaire

\mathcal{E}\setminus \left(\mathcal{D}_1\cup\cdots\cup\mathcal{D}_d\right)

de leur union. Ce sont des polygones convexes, certains bornés, d’autres pas, dont les côtés sont des segments des \mathcal{D}_i.

Leur nombre dépend non seulement de celui des droites mais aussi de la façon dont celles-ci se coupent. Voici un exemple où 5 droites déterminent 15 régions :

regions

Il est clair qu’on obtieindrait 16 régions en déplaçant légèrement, parallèlement à elle-même, une des droites passant par le point noté « Double » sur la figure.

Nous dirons d’un point de l’union des droites \mathcal{D}_i qu’il est de multiplicité m s’il appartient à exactement m+1 d’entre elles : il est ainsi simple s’il appartient à exactement deux de ces droites, double si c’est à trois, et ainsi de suite. Cela étant, il est facile de vérifier, par récurrence sur l’entier d\geq 0, que

Le nombre r de régions déterminées par d droites de \mathcal E vaut

(1) r=1+d+p

p est la somme des multiplicités des points en lesquels ces droites se coupent.

Cette propriété est évidemment vraie en l’absence de droite car dans ce cas, d=p=0 et il n’y a qu’une région : \mathcal E tout entier.

De plus, si elle est vérifiée pour la configuration déterminée par des droites \mathcal{D}_1,...,\mathcal{D}_d, elle l’est aussi pour celle obtenue en leur adjoignant une droite supplémentaire \mathcal{D}^*.

En effet, par convexité, si une région déterminée par les \mathcal{D}_i rencontre \mathcal{D}^*, elle est partagée en deux par celle-ci et la coupe selon un segment de droite dont chaque extrémité est sur une des autres droites. Dès lors, en supposant que \mathcal{D}^* coupe les droites \mathcal{D}_i en k points P_1,...,P_k, elle crée k+1 nouvelles régions lorsqu’on la leur adjoint. En même temps, la multiplicité totale des points d’intersection augmente de k car ceux des P_j qui ne sont pas intersections de \mathcal{D}_i — les nouveaux points — sont de multiplicité 1 tandis que les autres voient leur multiplicité augmenter d’une unité.

Tout cela est illustré sur la figure suivante dans laquelle la droite ajoutée est dessinée en rouge.

regions_2

Au total, lorsqu’on adjoint \mathcal{D}^* à \mathcal{D}_1,...,\mathcal{D}_d, les deux membres de (1) augmentent de k+1 et la propriété est donc établie.

En relisant attentivement la preuve ci-dessus, on constaterait aisément que le nombre de régions délimitées par d droites est maximum lorsque toutes leurs intersections sont simples de sorte que(*)

r\leq 1+d+{d \choose 2}=\frac 1 2 (d^2+d+2)

J’en viens alors à la question qui m’intrigue dont je parlais en début de texte. Elle trouve son origine dans cette valeur maximale r(d) que nous venons de trouver pour r.

Ayant choisi un repère affine de \mathcal{E}, nous pouvons représenter des droites \mathcal{D}_1,...,\mathcal{D}_d par des équations \alpha_1=0,...,\alpha_d=0 du premier degré à deux inconnues. L’union des droites est le lieu des points dont les coordonnées vérifient l’équation \alpha_1\cdots\alpha_d=0 tandis que l’intérieur de chaque région délimitée par les droites est caractérisé par un système d’inégalités

(2) \pm\alpha_1>0,...,\pm\alpha_d>0

Ces systèmes sont en nombre

2^d=(1+1)^d=\underbrace{1+d+{d\choose 2}}_{=r(d)}+\cdots

Dès que d dépasse 2, il y en a donc plus qu’il n’y a de régions, et de plus en plus à mesure que d grandit!

A dire vrai, si je comprends géométriquement le phénomène je ne m’explique pas algébriquement pourquoi tout au plus r(d) de ces systèmes sont compatibles.

Déjà pour 3 équations, le problème est intrigant. Je vous propose ainsi de montrer par des moyens purement algébriques que si d=3, un au moins des huit systèmes (2) n’a pas de solutions(**).

__________
(*) Lorsque les intersections sont simples, il y en a {d\choose 2}, à savoir une par paire de droites. Je reviendrai sur le fait que la borne supérieure indiquée de r est atteinte dans un billet ultérieur.
(**) Naturellement, on suppose que pour i\neq j, \alpha_i et \alpha_j ne sont pas proportionnels.

Publicités

6 réflexions sur “Régions déterminées par des droites d’un plan

  1. Pour d=3, quitte à multiplier les \alpha_i par des constantes >0 et quitte à les permuter, on a une relation du type \alpha_3=\alpha_1+\alpha_2, donc les relations \alpha_1>0, \alpha_2>0, \alpha_3<0, je ne vois pas pour l’instant…

  2. Desole pour les erreurs des messages precedents. Voici le message correct :

    Pour d=3, si deux quelconques des droites ne sont pas paralleles, quitte à multiplier les \alpha_i par des constantes non nulles, on a une relation du type \alpha_3=\alpha_1+\alpha_2 + c avec c positif ou nul, donc les relations \alpha_1 > 0, \alpha_2 > 0 et $latex \alpha_3 3, je ne vois pas…

  3. Je peux corriger vos messages et supprimer les doublons comme vous le souhaitez.

    J’avais effectivement pensé à une application du lemme de Farkas mais je n’ai encore rien trouvé de convainquant.

  4. Pingback: Découpons le plan | Blogdemaths

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s