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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

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

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

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

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

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

Другое доказательство было дано Ловашом и Шрайвером. ^[3] Третье доказательство дано Матоусеком: ^{[4] : 115}

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

Приложения

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

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

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

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

Связанные концепции

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

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

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

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

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

Примечания

1. Кларксон и др. (1996).
2. Баймоци, Е.Г.; Барань, И. (1 сентября 1979 г.). «Об общем обобщении теоремы Борсука и Радона». Acta Mathematica Academiae Scientiarum Hungaricae . 34 (3): 347–350. дои : 10.1007/BF01896131. ISSN  1588-2632. S2CID  12971298.
3. Ловас, Ласло; Шрайвер, Александр (1998). «Теорема Борсука для антиподальных связей и спектральная характеристика графов, не имеющих связей, которые можно вложить». Труды Американского математического общества . 126 (5): 1275–1285. doi : 10.1090/S0002-9939-98-04244-0 . ISSN  0002-9939. S2CID  7790459.
4. Матоушек, Йиржи (2007). Использование теоремы Борсука-Улама : Лекции по топологическим методам в комбинаторике и геометрии (2-е изд.). Берлин-Гейдельберг: Springer-Verlag. ISBN 978-3-540-00362-5. Написано в сотрудничестве с Андерсом Бьёрнером и Гюнтером М. Циглером., Раздел 4.3
5. Cieslik, Dietmar (2006), Кратчайшая связность: Введение с приложениями в филогении, комбинаторная оптимизация, т. 17, Springer, стр. 6, ISBN 9780387235394.
6. Пластриа, Франк (2006), «Повторный взгляд на проблемы размещения четырех точек Ферма. Новые доказательства и расширения старых результатов» (PDF) , Журнал IMA по управленческой математике , 17 (4): 387–396, doi :10.1093/imaman/dpl007, Zbl  1126.90046.
7. Матоушек (2002), стр. 11.
8. Эпсилон-сети и VC-измерение, Конспект лекций Марко Пеллегрини, 2004.
9. Кей и Уомбл (1971).
10. Дюше (1987).

Ссылки

• Баймоци, Е.Г.; Барань И. (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. Symp. Pure Math., т. 7, Американское математическое общество , стр. 101–179.
• Дюше, Пьер (1987), «Выпуклые множества в графах. II. Минимальная выпуклость пути», Журнал комбинаторной теории, Серия A , 44 (3): 307–316, doi : 10.1016/0095-8956(88)90039-1. Цитируется Bandelt & Pesch (1989).
• Экхофф, Дж. (1993), «Теоремы типа Хелли, Радона и Каратеодори», Справочник по выпуклой геометрии , т. A, B, Амстердам: Северная Голландия, стр. 389–448.
• Кей, Дэвид К.; Уомбл, Юджин В. (1971), «Аксиоматическая теория выпуклости и соотношения между числами Каратеодори, Хелли и Радона», Pacific Journal of Mathematics , 38 (2): 471–485, doi : 10.2140/pjm.1971.38.471 , MR  0310766.
• Матоушек, Й. (2002), «1.3 Лемма Радона и теорема Хелли», Лекции по дискретной геометрии , Graduate Texts in Mathematics , т. 212, Springer-Verlag, стр. 9–12, ISBN 978-0-387-95373-1.
• Матоушек, Й. (2003), «5.1 Теоремы невложимости: Введение», Использование теоремы Борсука–Улама: Лекции по топологическим методам в комбинаторике и геометрии , Springer-Verlag, стр. 88–92.
• Радон, Дж. (1921), «Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten», Mathematische Annalen , 83 (1–2): 113–115, doi : 10.1007/BF01464231, S2CID  121627696.
• Тверберг, Х. (1966), «Обобщение теоремы Радона», Журнал Лондонского математического общества , 41 : 123–128, doi :10.1112/jlms/s1-41.1.123.