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

В геометрії, теорема Радона на опуклих множинах, опублікована у 1921, стверджує, що будь-яку множину з d + 2 точок в R^d можна розбити на дві неперетинні множини, чиї опуклі оболонки перетинаються. Точка, що належить перетину цих опуклих оболонок, називається точка Радона множини.

Наприклад, у цьому випадку d = 2, будь-яка множина з чотирьох точок на евклідовій площині розбивна одним з двох способів. Вона може утворити трійку і одинака, де опукла оболонка трійки містить одинака; або ж, вона може утворити дві пари точок, так що ці точки формують кінці відрізків, що перетинаються.

Доведення і побудова

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

Розглянемо довільну множину ${\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 та ін., (1996).

Посилання

• Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (1996), (PDF), Int. J. Computational Geometry & Applications, 6 (3): 357—377, doi:10.1142/s021819599600023x, MR 1409651, архів оригіналу (PDF) за 22 лютого 2012, процитовано 3 липня 2018.