Théorème de Radon (géométrie)

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

[modifier] Énoncé

Le théorème de Radon, ou lemme de Radon, sur les ensembles convexes affirme que tout ensemble A = \{a_1, \dots, a_{d+2}\} contenant d + 2 éléments de \mathbb{R}^{d} admet une partition en deux parties A1,A2 dont les enveloppes convexes Conv(A1) et Conv(A2) se rencontrent. Une telle partition est alors appelée partition de Radon, et un point de l'intersection des enveloppes est appelé point de Radon (il ne s'agit pas a priori d'un des points ai).

Prenons l'exemple d = 2. Dans ce cas l'ensemble A est constitué de quatre points. La partition de A peut donner un ensemble de trois points et un singleton, les premiers formant un triangle contenant le dernier point. Ou alors la partition consiste en deux ensembles constitués chacun de deux points, les segments s'intersectant en un point.

Ce résultat a été publié pour la première fois par Johann Radon en 1921[1]. Il y apparaît comme résultat intermédiaire dans la preuve du théorème de Helly, ce qui explique la dénomination courante de lemme[2].

[modifier] Preuve

On suppose que X = \{a_1,\dots,a_{d+2}\}\subset \mathbf{R}^d. Considérons le système :

\sum_{j=1}^{d+2} \lambda_j a_j=0

\sum_{j=1}^{d+2} \lambda_j=0

d'inconnues réelles \lambda_1,\dots,\lambda_{d+2} : il équivaut à un système linéaire de d + 1 équations à d + 2 inconnues a_1,a_2,\dots,a_{d+2}, puisque la première équation, si on la développe en un système pour chaque composante des ai (vecteurs dans \mathbf{R}^d), se transforme aussitôt en d équations linéaires traditionnelles. Il existe donc une solution non nulle de ce système. Fixons \lambda_1,\lambda_2,\dots,\lambda_{d+2} une telle solution. Posons alors :

I_1 = \{i\,\mid\, \lambda_i > 0\}

I_2 = \{i\,\mid\, \lambda_i \leq 0\}

Puisque la somme des λi est nulle alors que les λi ne sont pas tous nuls, I et J ne sont pas vides.

La partition requise de A est alors A_1=\{x_i\,\mid\, i\in I_1\} et A_2=\{x_i\,\mid\, i\in I_2\}. En effet, il est immédiat de vérifier à partir du système, que :

\frac{\displaystyle\sum_{i\in I_1} a_i x_i}{\displaystyle\sum_{i\in I_1} a_i} = \frac{\displaystyle\sum_{i\in I_2} a_i x_i}{\displaystyle\sum_{i\in I_2} a_i}

et cette formule fournit un point commun aux enveloppes convexes de A1 et de A2.

[modifier] Théorème de Tverberg

Helge Tverberg a démontré en 1966 une généralisation de ce théorème pour des partitions de A en r sous-ensembles. Le théorème de Tverberg affirme que :

Un ensemble A de 1 + (d + 1)(r − 1) points de \mathbb{R}^d admet une partition en r sous-ensembles dont l'intersection des enveloppes convexes n'est pas vide

[modifier] Notes et références

  1. ↑ Johann Radon, Mengen konvexer körper, die einen gemeinsamen Punkt enthalten, Math. Ann., 83:113-115, 1921
  2. ↑ Jiri Matousek, Lectures on Discrete Geometry, Graduate Texts in Mathematics, Springer, 2002
  • H. G. Eggleston, Convexity, Cambridge Univ. Press.
  • S. R. Lay, Convex Sets and Their Applications, Wiley.
Autres langues