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

В геометрии : теорема Радона о выпуклых множествах , опубликованная Иоганном Радоном в 1921 году, гласит, что

Любой набор из d + 2 точек в R ^д можно разбить на два множества, выпуклые оболочки которых пересекаются.

Точка пересечения этих выпуклых оболочек называется точкой Радона множества.

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

Например, в случае d = 2 любой набор из четырех точек евклидовой плоскости можно разделить одним из двух способов. Он может образовывать тройку и синглтон, где выпуклая оболочка тройки (треугольник) содержит синглтон; альтернативно, он может образовывать две пары точек, которые образуют конечные точки двух пересекающихся отрезков линии .

Доказательство и конструкция

Рассмотрим любой набор $X=\{x_{1},x_{2},\dots ,x_{d+2}\}\subset \mathbf {R} ^{d}$ d + 2 точек в d -мерном пространстве. Тогда существует набор множителей a ₁ , ..., a _{d + 2} , не все из которых равны нулю, решающий систему линейных уравнений

$\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\subseteq X$ — множество точек с положительными множителями, и пусть $J=X\setminus I$ быть набором точек с отрицательными или нулевыми множителями. Затем $I$ и $J$ сформируем искомое разбиение точек на два подмножества с пересекающимися выпуклыми оболочками.

Выпуклые оболочки $I$ и $J$ должны пересечься, поскольку они оба содержат точку

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

где

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

Левая часть формулы для $p$ выражает эту точку как выпуклую комбинацию точек в $I$, а правая часть выражает ее как выпуклую комбинацию точек $J$. Поэтому, $p$ принадлежит обеим выпуклым оболочкам, что завершает доказательство.

Этот метод доказательства позволяет эффективно построить точку Радона за полиномиальное по размеру время, используя метод исключения Гаусса или другие эффективные алгоритмы для решения системы уравнений для множителей.

Топологическая теорема Радона

Эквивалентная формулировка теоремы Радона:

Если ƒ — любая аффинная функция из ( d + 1)-мерного симплекса Δ ^д+1 в Р ^д , то существуют две непересекающиеся грани Δ ^д+1 чьи изображения под ƒ пересекаются.

Они эквивалентны, поскольку любая аффинная функция на симплексе однозначно определяется образами его вершин. Формально, пусть ƒ — аффинная функция из ∆ ^д+1 в Р ^д . Позволять $v_{1},v_{2},\dots ,v_{d+2}$ — вершины ∆ ^д+1 , и пусть $x_{1},x_{2},\dots ,x_{d+2}$ быть их изображениями под ƒ . По оригинальной формулировке, $x_{1},x_{2},\dots ,x_{d+2}$ можно разделить на два непересекающихся подмножества, например ( x _i ) _{i в I} и ( x _j ) _{j в J,} с перекрывающейся выпуклой оболочкой. Поскольку f аффинно, выпуклая оболочка ( x _i ) _{i в I} является образом грани, натянутой на вершины ( vi ₎ i _{в I} , и аналогично выпуклая оболочка ( x _j )j _{в J} является образом грани, натянутой на вершины ( v _j )j _{в j} . Эти две грани не пересекаются, а их образы под f пересекаются – как утверждает новая формулировка. Топологическая теорема Радона обобщает эту формулировку. Это позволяет f быть любой непрерывной функцией, не обязательно аффинной:

Если ƒ — любая непрерывная функция из ( d + 1)-мерного симплекса Δ ^д+1 в Р ^д , то существуют две непересекающиеся грани Δ ^д+1 чьи изображения под ƒ пересекаются.

В более общем смысле, если K — любой ( d + 1)-мерный компактный выпуклый набор, а ƒ — любая непрерывная функция от K до d -мерного пространства, то существует линейная функция g такая, что некоторая точка, в которой g достигает своего максимального значения, и некоторые другие точки, в которых g достигает минимального значения, отображаются с помощью ƒ в ту же точку. В случае, когда K является симплексом, две грани симплекса, образованные точками максимума и минимума g, должны быть двумя непересекающимися гранями, изображения которых имеют непустое пересечение. Это же общее утверждение, примененное к гиперсфере , а не к симплексу, дает теорему Борсука-Улама о том, что ƒ должен отображать две противоположные точки сферы в одну и ту же точку.

Доказательства

Топологическая теорема Радона была первоначально доказана Баймочи и Барани. следующим образом:

• Построим непрерывное отображение g из S ^д (d-мерная сфера ) на ∆ ^д+1 , такой, что для каждой точки x на сфере g ( x ) и g (- x ) находятся на двух непересекающихся гранях Δ ^д+1 .
• Примените теорему Борсука–Улама к функции $f\circ g$, которая является непрерывной функцией из S ^д в Р ^д . Теорема гласит, что для любой такой функции существует некоторая точка y на S ^д , такой, что f(g(y)) = f(g(-y)).
• Точки g(y) и g(-y) лежат на двух непересекающихся гранях ∆ ^д+1 , и они отображаются посредством f в одну и ту же точку R ^д . Это означает, что изображения этих двух непересекающихся лиц пересекаются.

Другое доказательство было дано Ловасом и Шрийвером. Третье доказательство дает Матоусек:

• Пусть K – симплекс ∆ ^д+1 , и пусть $K_{\Delta }^{*2}$ быть удаленным соединением K с самим собой.
• Геометрическая реализация $K_{\Delta }^{*2}$ гомеоморфна сфере S ^д+1 .
• , Z ₂ -индекс Следовательно $K_{\Delta }^{*2}$ равно d +1.
• Топологическая теорема Радона следует из следующей более общей теоремы. Для любого симплициального комплекса K , если Z ₂ -индекс $K_{\Delta }^{*2}$ больше d , то для любого непрерывного отображения из || К || в Р ^д , изображения двух непересекающихся граней K пересекаются.

Приложения

Точка Радона любых четырех точек на плоскости — это их геометрическая медиана , точка, которая минимизирует сумму расстояний до других точек.

Теорема Радона является ключевым шагом стандартного доказательства теоремы Хелли о пересечении выпуклых множеств; это доказательство послужило мотивацией для первоначального открытия Радоном теоремы Радона.

Теорему Радона также можно использовать для расчета размерности VC d - мерных точек относительно линейных разделений. Существуют множества из d + 1 точек (например, точки регулярного симплекса) такие, что любые два непустых подмножества можно отделить друг от друга гиперплоскостью. Однако независимо от того, какой набор из d + 2 точек задан, два подмножества разбиения Радона не могут быть линейно разделены. Следовательно, размерность VC этой системы равна ровно d + 1.

, Рандомизированный алгоритм который неоднократно заменяет наборы из d + 2 точек их точкой Радона, можно использовать для вычисления приближения к центральной точке любого набора точек за время, полиномиальное как по количеству точек, так и по размерности.

Связанные понятия

Геометрическая медиана . Точка Радона трех точек в одномерном пространстве — это не что иное, как их медиана . Геометрическая медиана набора точек — это точка, минимизирующая сумму расстояний до точек набора; он обобщает одномерную медиану и изучался как с точки зрения местоположения предприятия, так и с точки зрения надежной статистики . Для наборов из четырех точек на плоскости геометрическая медиана совпадает с точкой Радона.

Теорема Тверберга . Обобщение разделения на r множеств было дано Хельге Твербергом ( 1966 ) и теперь известно как теорема Тверберга . В нем говорится, что для любого набора $(d+1)(r-1)+1\$точек евклидова d -пространства существует разбиение на r подмножеств, выпуклые оболочки которых пересекаются хотя бы в одной общей точке.

Теорема Каратеодори утверждает, что любая точка выпуклой оболочки некоторого набора точек также находится внутри выпуклой оболочки подмножества, состоящего не более чем из d + 1 точек; то есть данная точка является частью разбиения Радона, в котором она является одноэлементной. В одном доказательстве теоремы Каратеодори используется метод исследования решений систем линейных уравнений, аналогичный доказательству теоремы Радона, для исключения одной точки за раз, пока не останется не более d + 1.

Выпуклая геометрия . Концепции, связанные с теоремой Радона, также рассматривались для выпуклых геометрий , семейств конечных множеств со свойствами, согласно которым пересечение любых двух множеств в семействе остается в семействе, а пустое множество и объединение всех множеств принадлежат семейству. семья. В этом более общем контексте выпуклая оболочка множества S — это пересечение членов семейства, содержащих S , а число Радона пространства — это наименьшее r, такое, что любые r точек имеют два подмножества, выпуклые оболочки которых пересекаются. Аналогично можно определить число Хелли h и число Каратеодори c по аналогии с их определениями для выпуклых множеств в евклидовых пространствах и показать, что эти числа удовлетворяют неравенствам h < r ⩽ ch + 1.

Теорема Радона для графов . В произвольном неориентированном графе можно определить выпуклое множество как набор вершин, который включает в себя каждый индуцированный путь, соединяющий пару вершин в наборе. Согласно этому определению, каждое множество из ω + 1 вершин в графе можно разбить на два подмножества, выпуклые оболочки которых пересекаются, и ω + 1 — минимальное число, для которого это возможно, где ω — кликовое число данного графа. Соответствующие результаты, включающие кратчайшие пути вместо индуцированных путей, см. в Chepoi (1986) и Bandelt & Pesch (1989) .

Ссылки

• Баймоци, Е.Г.; Барань И. (1979), «Общее обобщение теоремы Борсука и Радона», Acta Mathematica Hungarica , 34 (3–4): 347–350, doi : 10.1007/BF01896131 , S2CID   12971298 .
• Бандельт, Х.-Ю.; Пеш, Э. (1989), «Теорема Радона для графов Хелли», Archiv der Mathematik , 52 (1): 95–98, doi : 10.1007/BF01197978 , S2CID   120983560 .
• Чепой, В.Д. (1986), "Некоторые свойства d-выпуклости в триангулированных графах", Матем. Исслед. (на русском языке), 87 : 164–177 . Цитируется Bandelt & Pesch (1989) .
• Кларксон, Кеннет Л .; Эппштейн, Дэвид ; Миллер, Гэри Л .; Стертивант, Карл; Тенг, Шан-Хуа (1996), «Аппроксимация центральных точек с помощью итерированных точек Радона» , Международный журнал вычислительной геометрии и приложений , 6 (3): 357–377, doi : 10.1142/s021819599600023x , MR   1409651 .
• Данцер, Л.; Грюнбаум, Б. ; Клее, В. (1963), «Теорема Хелли и ее родственники», Выпуклость , Proc. Симп. Чистая математика., вып. 7, Американское математическое общество , стр. 101–179 .
• Дюше, Пьер (1987), «Выпуклые множества в графах. II. Минимальная выпуклость пути», Журнал комбинаторной теории, серия A , 44 (3): 307–316, doi : 10.1016/0095-8956(88)90039-1 . Цитируется Bandelt & Pesch (1989) .
• Экхофф, Дж. (1993), «Теоремы типа Хелли, Радона и Каратеодори», Справочник по выпуклой геометрии , том. А, Б, Амстердам: Северная Голландия, стр. 389–448 .
• Кей, Дэвид С.; Уомбл, Юджин В. (1971), «Аксиоматическая теория выпуклости и взаимосвязь между числами Каратеодори, Хелли и Радона» , Pacific Journal of Mathematics , 38 (2): 471–485, doi : 10.2140/pjm.1971.38.471 , МР   0310766 .
• Матушек, Дж. (2002), «1.3 Лемма Радона и теорема Хелли», Лекции по дискретной геометрии , Тексты для аспирантов по математике , том. 212, Springer-Verlag, стр. 9–12, ISBN.  978-0-387-95373-1 .
• Матушек, Дж. (2003), «Теоремы 5.1 о невложимости: введение», Использование теоремы Борсука – Улама: Лекции по топологическим методам в комбинаторике и геометрии , Springer-Verlag, стр. 88–92 .
• Радон, Дж. (1921), «Наборы выпуклых тел, содержащих общую точку», Mathematical Annals , 83 (1–2): 113–115, doi : 10.1007/BF01464231 , S2CID   121627696 .
• Тверберг, Х. (1966), «Обобщение теоремы Радона», Журнал Лондонского математического общества , 41 : 123–128, doi : 10.1112/jlms/s1-41.1.123 .