В геометрии , теорема Радона на выпуклых множествах , опубликованный Иоганн Радон в 1921 г., утверждает , что любой набор д +-в точках R D может быть распределял на два множество, выпуклые оболочки которых пересекаются. Точка пересечения этих выпуклых оболочек называется радоновской точкой множества.
Например, в случае d = 2 любой набор из четырех точек на евклидовой плоскости можно разделить одним из двух способов. Он может образовывать тройку и одноэлемент, где выпуклая оболочка тройки (треугольник) содержит одноэлемент; в качестве альтернативы, он может образовывать две пары точек, которые образуют конечные точки двух пересекающихся отрезков прямой .
Доказательство и конструкция
Рассмотрим любой набор из D + 2 точек в г - мерном пространстве. Тогда существует набор множителей a 1 , ..., a d + 2 , не все из которых равны нулю, решающий систему линейных уравнений
потому что есть d + 2 неизвестных (множителей), но только d + 1 уравнений, которым они должны удовлетворять (по одному для каждой координаты точек, вместе с окончательным уравнением, требующим, чтобы сумма множителей была равна нулю). Зафиксируем какое-нибудь конкретное ненулевое решение a 1 , ..., a d + 2 . Позволять - множество точек с положительными множителями, и пусть - набор точек с отрицательными или нулевыми множителями. потом а также образуют требуемое разбиение точек на два подмножества с пересекающимися выпуклыми оболочками.
Выпуклые оболочки а также должны пересекаться, потому что оба содержат точку
где
Левая часть формулы для выражает эту точку как выпуклую комбинацию точек в, а правая часть выражает его как выпуклую комбинацию точек в . Следовательно, принадлежит обеим выпуклым оболочкам, завершая доказательство.
Этот метод доказательства позволяет эффективно построить точку Радона за время, полиномиальное по размерности, с помощью исключения Гаусса или других эффективных алгоритмов для решения системы уравнений для множителей. [1]
Топологическая теорема Радона
Топологическое обобщение теоремы Радона состояний , что, если ƒ любая непрерывная функция от ( г + 1) -мерном симплекс к д - мерное пространство, то симплекс имеет два лица , чьи образы непересекающиеся под ƒ не пересекаются. [2] Сама теорема Радона может быть интерпретирована как частный случай, когда ƒ - единственное аффинное отображение, которое переводит вершины симплекса в заданное множество d + 2 точек в d -мерном пространстве.
В более общем смысле, если K - любое ( d + 1) -мерное компактное выпуклое множество, а ƒ - любая непрерывная функция из K в d -мерное пространство, то существует линейная функция g такая, что некоторая точка, в которой g достигает своего максимального значения, и некоторая другая точка, в которой g достигает минимального значения, отображается символом в ту же точку. В случае, когда K - симплекс, две симплексные грани, образованные точками максимума и минимума g, должны быть двумя непересекающимися гранями, образы которых имеют непустое пересечение. Это же общее утверждение, примененное к гиперсфере вместо симплекса, дает теорему Борсука – Улама о том , что ƒ должно отображать две противоположные точки сферы в одну и ту же точку. [2]
Приложения
Точка Радона любых четырех точек на плоскости является их геометрической медианой , точкой, которая минимизирует сумму расстояний до других точек. [3] [4]
Теорема Радона является ключевым этапом стандартного доказательства теоремы Хелли о пересечениях выпуклых множеств; [5] это доказательство послужило мотивом для первоначального открытия Радоном теоремы Радона.
Теорема Радон также может быть использована для вычисления размерности VC в д - мерных точек относительно линейных расстояний. Существуют наборы из d + 1 точек (например, точки регулярного симплекса) такие, что любые два непустых подмножества можно отделить друг от друга гиперплоскостью. Однако независимо от того, какой набор из d + 2 точек задан, два подмножества радонового разбиения не могут быть разделены линейно. Следовательно, размерность ВК этой системы в точности равна d + 1. [6]
Рандомизированное алгоритм , который многократно заменяет наборы д + 2 точек с их точкой Радона можно использовать для вычисления приближения к центральной точке любого множества точек, в количестве времени , которое является многочленом как по числу точек и размерности. [1]
Связанные понятия
Точка Радона трех точек в одномерном пространстве - это просто их медиана . Геометрические средняя из множества точек является точкой минимизации суммы расстояний до точек в наборе; он обобщает одномерную медиану и был изучен как с точки зрения расположения объекта, так и с точки зрения надежной статистики . Для наборов из четырех точек на плоскости геометрическая медиана совпадает с точкой Радона.
Другое обобщение для разбиения на r множеств было дано Хельге Твербергом ( 1966 ) и теперь известно как теорема Тверберга . В нем говорится, что для любого набора
точек в евклидовом d -пространстве существует разбиение на r подмножеств, выпуклые оболочки которых пересекаются хотя бы в одной общей точке.
Теорема Каратеодори утверждает, что любая точка в выпуклой оболочке некоторого набора точек также находится внутри выпуклой оболочки подмножества не более чем d + 1 точек; то есть, данная точка является частью радонового разбиения, в котором она одноэлементна. Одно доказательство теоремы Каратеодори использует технику исследования решений систем линейных уравнений, аналогичную доказательству теоремы Радона, для устранения одной точки за раз, пока не останется не более d + 1.
Концепции, связанные с теоремой Радона, также рассматривались для выпуклой геометрии , семейств конечных множеств со свойствами, согласно которым пересечение любых двух множеств в семействе остается в семействе и что пустое множество и объединение всех множеств принадлежит семейству семья. В этом более общем контексте выпуклая оболочка множества S - это пересечение членов семейства, которые содержат S , а число Радона пространства - это наименьшее r такое, что любые r точек имеют два подмножества, выпуклые оболочки которых пересекаются. Аналогичным образом можно определить число Хелли h и число Каратеодори c по аналогии с их определениями для выпуклых множеств в евклидовых пространствах, и можно показать, что эти числа удовлетворяют неравенствам h < r ≤ ch + 1. [7]
В произвольном неориентированном графе можно определить выпуклое множество как набор вершин, который включает в себя каждый индуцированный путь, соединяющий пару вершин в множестве. С помощью этого определения каждый набор из ω + 1 вершин в графе может быть разбит на два подмножества, выпуклые оболочки которых пересекаются, и ω + 1 - минимальное число, для которого это возможно, где ω - кликовое число данного графа. [8] По поводу связанных результатов, касающихся кратчайших путей вместо индуцированных, см. Chepoi (1986) и Bandelt & Pesch (1989) .
Заметки
- ^ a b Кларксон и др. (1996) .
- ^ а б Баймочи и Барани (1979) ; Матушек (2003) .
- ^ Цислик Дитмар (2006), Кратчайшее подключение: Введение с приложениями в филогенезе , комбинаторная оптимизация, 17 , Springer, стр. 6, ISBN 9780387235394.
- ^ Пластрия, Франк (2006), « Пересмотр четырехточечных проблем размещения Ферма. Новые доказательства и расширения старых результатов» (PDF) , IMA Journal of Management Mathematics , 17 (4): 387–396, doi : 10.1093 / imaman / dpl007 , Zbl 1126,90046 CS1 maint: обескураженный параметр ( ссылка ).
- ^ Матушек (2002) , стр. 11.
- ^ Эпсилон-сети и VC-измерение , Лекционные заметки Марко Пеллегрини, 2004.
- ^ Kay & Уомбл (1971) .
- ^ Duchet (1987) .
Рекомендации
- Bajmóczy, EG; Барань, И. (1979), "Общее обобщение Борсука и теоремы Радона", Acta Mathematica Hungarica , 34 (3-4): 347-350, DOI : 10.1007 / BF01896131.
- Bandelt, H.J .; Пеш, E. (1989), "Теорема Радона для графов Хелли", Archiv дер Mathematik , 52 (1): 95-98, DOI : 10.1007 / BF01197978.
- Чепой, В. Д. (1986), "Некоторые свойства d-выпуклости в триангулированных графах", Матем. Исслед. (на русском языке), 87 : 164–177. Цитируется Bandelt & Pesch (1989) .
- Кларксон, Кеннет Л .; Эпштейн, Дэвид ; Миллер, Гэри Л .; Стуртивант, Карл; Тен, Шан-Хуа (1996), "Аппроксимация центральные точки с итеративных точек Радона" (PDF) , Международный журнал вычислительной геометрии и приложений , 6 (3): 357-377, DOI : 10,1142 / s021819599600023x , МР 1409651.
- Danzer, L .; Грюнбаум, Б .; Клее, В. (1963), "Теорема Хелли и ее родственники", Выпуклость , Proc. Symp. Pure Math., 7 , Американское математическое общество , стр. 101–179..
- Duchet, Пьер (1987), "Выпуклые множества в графах II Минимальный путь выпуклость..", Журнал комбинаторной теории, Серия А , 44 (3): 307-316, DOI : 10,1016 / 0095-8956 (88) 90039-1. Цитируется Bandelt & Pesch (1989) .
- Экхофф, Дж. (1993), "Теоремы типа Хелли, Радона и Каратеодори", Справочник по выпуклой геометрии , A, B , Амстердам: Северная Голландия, стр. 389–448..
- Кей, Дэвид С .; Уомбл Евгений W. (1971), "Теория Axiomatic выпуклость и отношения между числами Каратеодори, Хелли и Радона" , Тихоокеанский журнал математики , 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), "Mengen konvexer Körper, умирают Einen gemeinsamen Punkt enthalten", Mathematische Annalen , 83 (1-2): 113-115, DOI : 10.1007 / BF01464231.
- Тверберга, H. (1966), "Обобщение теоремы Радона" (PDF) , журнал Лондонского математического общества , 41 : 123-128, DOI : 10.1112 / jlms / s1-41.1.123[ мертвая ссылка ] .