Введение

Утверждается, что d+2 точки в d измерениях можно разбить на два подмножества, выпуклые оболочки которых пересекаются. В геометрии теорема Радона о выпуклых множествах, опубликованная Иоганном Радоном в 1921 году, гласит: любое множество, состоящее из d+2 точек в Rd, можно разбить на два подмножества, выпуклые оболочки которых пересекаются. Точка в пересечении этих выпуклых оболочек называется точкой Радона для данного множества. Например, в случае d=2, любое множество из четырех точек на евклидовой плоскости можно разбить одним из двух способов. Можно образовать тройку и одиночную точку, при этом выпуклая оболочка тройки (треугольник) содержит одиночную точку; либо можно образовать две пары точек, являющиеся концами двух пересекающихся отрезков прямой.

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

Эквивалентная формулировка теоремы Радона: если ƒ — любая аффинная функция из (d + 1)-мерного симплекса Δd+1 в Rd, то существуют две непересекающиеся грани Δd+1, чьи образы под действием ƒ пересекаются. Они эквивалентны, поскольку любая аффинная функция на симплексе однозначно определяется образами его вершин. Формально, пусть ƒ — аффинная функция из Δd+1 в Rd. Пусть — вершины Δd+1, и пусть — их образы под действием ƒ. Согласно исходной формулировке, множество вершин можно разбить на два непересекающихся подмножества, например, (xi)i ∈ I и (xj)j ∈ J, с перекрывающимися выпуклыми оболочками. Поскольку f аффинна, выпуклая оболочка (xi)i ∈ I является образом грани, образованной вершинами (vi)i ∈ I, и аналогично выпуклая оболочка (xj)j ∈ J является образом грани, образованной вершинами (vj)j ∈ J. Эти две грани не пересекаются, и их образы под действием f пересекаются, как и утверждается в новой формулировке. Топологическая теорема Радона обобщает эту формулировку. Она позволяет f быть любой непрерывной функцией, не обязательно аффинной, следующим образом:

Построим непрерывное отображение g из Sd (d-мерной сферы) в Δd+1, такое, что для каждой точки x на сфере, g(x) и g(-x) лежат на двух непересекающихся гранях Δd+1. Применим теорему Борсука — Улама к функции f∘g, которая является непрерывной функцией из Sd в Rd. Теорема утверждает, что для любой такой функции существует точка y на Sd, такая, что f(g(y)) = f(g(-y)). Точки g(y) и g(-y) лежат на двух непересекающихся гранях Δd+1, и они отображаются функцией f в одну и ту же точку в Rd. Это означает, что образы этих двух непересекающихся граней пересекаются. Другое доказательство было дано Ловашем и Шрайвером. Третье доказательство приведено Матусеком:

Пусть K — симплекс Δd+1, и пусть — удалённое соединение K с самим собой. Геометрическая реализация гомеоморфна сфере Sd+1. Следовательно, Z2-индекс равен d+1. Топологическая теорема Радона следует из следующей более общей теоремы. Для любого симплициального комплекса K, если Z2-индекс больше d, то для каждого непрерывного отображения из |K| в Rd образы двух непересекающихся граней K пересекаются.

Приложения

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