Теорема Радона

Дві множини кожна з чотирьох точок на площині (вершини квадрата і рівнобічний трикутник з центроїдом), множники, що розв'язують систему цих лінійних рівнянь для цих точок, і розбиття Радона утворене відокремленням точок з додатними множниками від точок з від'ємними множниками.

Розглянемо довільну множину ${\displaystyle \{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}}$ з d + 2 точок в d-вимірному просторі. Тоді існує множина множників a₁, ..., a_d + 2, не всі з яких рівні нулю, що розв'язує систему лінійних рівнянь

${\displaystyle \sum _{i=1}^{d+2}a_{i}x_{i}=0,\quad \sum _{i=1}^{d+2}a_{i}=0,}$

з того, що маємо d + 2 невідомих (множники), але лише d + 1 рівнянь, яким вони мають задовольняти (одна для кожної координати і кінцеве рівняння, що накладає умову на суму множників). Оберемо якийсь ненульовий розв'язок a₁, ..., a_d + 2. Нехай I буде множиною точок з додатними множниками і нехай J буде множиною точок з від'ємними множниками або нулем. Тоді I і J утворюють необхідний розподіл точок на дві підмножини, опуклі оболонки яких перетинаються.

Опуклі оболонки I і J повинні перетинатись, бо вони містять спільну точку

${\displaystyle p=\sum _{i\in I}{\frac {a_{i}}{A}}x_{i}=\sum _{j\in J}{\frac {-a_{j}}{A}}x_{j},}$

де

${\displaystyle A=\sum _{i\in I}a_{i}=-\sum _{j\in J}a_{j}.}$

Лівий бік формули для p виражає цю точку як опуклу комбінацію точок з I, а правий бік виражає як опуклу комбінацію точок з J. Отже, p приналежить обом опуклим оболонкам, завершуючи доведення.

Це доведення дозволяє ефективну побудову точки Радона, за час поліноміальний від вимірності, із використанням методу Гаусса або іншого ефективного алгоритму для розв'язання системи лінійних рівнянь для множників.[1]

• Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (1996). Approximating center points with iterated Radon points. Int. J. Computational Geometry & Applications 6 (3): 357–377. MR 1409651. doi:10.1142/s021819599600023x..