Радондар теоремасы - Radons theorem - Wikipedia

Жылы геометрия, Радон теоремасы қосулы дөңес жиынтықтар, жариялаған Иоганн Радон 1921 жылы кез-келген жиынтығы туралы айтады г. + 2 ұпай R^г. бола алады бөлінді екі жиынтыққа дөңес корпус қиылысады. Осы дөңес қабықтардың қиылысу нүктесі а деп аталады Радон нүктесі жиынтықтың

Мысалы, жағдайда г. = 2, кез-келген төрт нүктенің жиынтығы Евклидтік жазықтық екі жолдың бірімен бөлуге болады. Ол үштік пен синглтонды құруы мүмкін, онда үштіктің (үшбұрыштың) дөңес корпусында синглтон болады; баламалы, ол қиылысатын екі нүктенің соңғы нүктелерін құрайтын екі жұп нүкте құруы мүмкін сызық сегменттері.

Дәлелдеу және құрылыс

Жазықтықтағы төрт нүктенің екі жиынтығы (төртбұрыштың төбелері және центроидпен бірге теңбүйірлі үшбұрыш), осы нүктелер үшін үш сызықтық теңдеулер жүйесін шешетін көбейткіштер және оң көбейткіштері бар нүктелерді оңнан көбейту арқылы түзілген Радон бөлімдері. теріс көбейткіштері бар нүктелер.

Кез-келген жиынтықты қарастырыңыз ${ displaystyle X = {x_ {1}, x_ {2}, dots, x_ {d + 2} } subset mathbf {R} ^ {d}}$ туралы г. + 2 ұпай г.-өлшемдік кеңістік. Сонда көбейткіштер жиынтығы бар а₁, ..., а_г. + 2, олардың барлығы нөлге тең емес сызықтық теңдеулер жүйесі

${ displaystyle sum _ {i = 1} ^ {d + 2} a_ {i} x_ {i} = 0, quad sum _ {i = 1} ^ {d + 2} a_ {i} = 0 ,}$

өйткені бар г. + 2 белгісіз (көбейткіштер), бірақ тек г. + Олар орындауға тиісті 1 теңдеулер (нүктелердің әр координатасы үшін біреуі, көбейткіштердің қосындысы нөлге тең болатын соңғы теңдеумен бірге). Нөлдік емес шешімді түзетіңіз а₁, ..., а_г. + 2. Келіңіздер ${ displaystyle I subseteq X}$ оң көбейткіштері бар нүктелер жиыны болып, болсын ${ displaystyle J = X setminus I}$ көбейткіштері теріс немесе нөлге тең нүктелер жиыны болуы керек. Содан кейін ${ displaystyle I}$ және ${ displaystyle J}$ нүктелердің қажетті бөлігін қиылысатын дөңес корпустары бар екі ішкі жиынтыққа құрайды.

Дөңес корпустары ${ displaystyle I}$ және ${ displaystyle 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}.}$

Формуласының сол жағы ${ displaystyle p}$ осы тармақты а ретінде білдіреді дөңес тіркесім тармақтарының ${ displaystyle I}$, ал оң жағы оны нүктелердің дөңес тіркесімі ретінде көрсетеді ${ displaystyle J}$. Сондықтан, ${ displaystyle p}$ дәлелдеуді аяқтай отырып, екі дөңес корпусқа жатады.

Бұл дәлелдеу әдісі Радон нүктесін тиімді уақыт аралығында құруға мүмкіндік береді көпмүшелік қолдану арқылы өлшемде Гауссты жою немесе көбейткіштерге арналған теңдеулер жүйесін шешудің басқа тиімді алгоритмдері.^[1]

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

A топологиялық Радон теоремасын жалпылау, егер ƒ болса үздіксіз функция бастап (г. + 1) -өлшемді қарапайым дейін г.-өлшемдік кеңістік, содан кейін симплекстің екі айырылған беті болады, олардың ƒ астындағы суреттері сәйкес келмейді.^[2] Радон теоремасының өзін ƒ ерекше болатын ерекше жағдай деп түсіндіруге болады аффина картасы симплекстің шыңдарын берілген жиынтыққа жеткізетін г. + 2 ұпай г.-өлшемдік кеңістік.

Жалпы, егер Қ кез келген (г. + 1) -өлшемді ықшам дөңес жиынтық, ал ƒ - кез келген үздіксіз функция Қ дейін г.-өлшемдік кеңістік, онда сызықтық функция болады ж кейбіреулер қайда екенін көрсетеді ж оның максималды мәніне және тағы бір басқа нүктеге жетеді ж оның минималды мәні ƒ арқылы сол нүктеге дейін бейнеленеді. Бұл жағдайда Қ симплекс, екі максималды және минималды нүктелерінен түзілген екі симплекс беті ж содан кейін кескіндері бос емес қиылысатын екі бөлінбеген тұлға болуы керек. A-ға қолданылған кездегі бірдей жалпы мәлімдеме гиперфера симплекстің орнына Борсук-Улам теоремасы, бұл ƒ сфераның екі қарама-қарсы нүктелерін бірдей нүктеге дейін бейнелеуі керек.^[2]

Қолданбалар

Жазықтықтағы кез-келген төрт нүктенің Радон нүктесі олардікі геометриялық медиана, басқа нүктелерге дейінгі қашықтықтардың қосындысын минимумға келтіретін нүкте.^[3][4]

Радон теоремасы стандартты дәлелдеудің негізгі қадамын құрайды Хелли теоремасы дөңес жиынтықтардың қиылысында;^[5] бұл дәлел Радон теоремасын түпнұсқалық түрде ашуға түрткі болды.

Радон теоремасын да есептеу үшін қолдануға болады VC өлшемі туралы г.-сызықтық бөлінулерге қатысты өлшемді нүктелер. Жиынтықтары бар г. + 1 ұпай (мысалы, қарапайым симплекстің нүктелері), өйткені әрбір екі бос емес ішкі жиындар бір-бірінен гиперпланмен бөлінуі мүмкін. Алайда, қандай жиынтығы болмасын г. + 2 ұпай беріледі, Радон бөлімінің екі ішкі жиынын сызықтық түрде бөлуге болмайды. Сондықтан бұл жүйенің VC өлшемі дәл келеді г. + 1.^[6]

A рандомизацияланған алгоритм жиындарын бірнеше рет ауыстырады г. Анонын есептеу үшін олардың радондық нүктесінің 2 ұпайын пайдалануға болады жуықтау а орталық нүкте нүктелер саны бойынша да, өлшем бойынша да көпмүшелік болатын кез келген нүкте жиынтығының.^[1]

Байланысты ұғымдар

Бір өлшемді кеңістіктегі үш нүктенің Радон нүктесі тек олар медиана. The геометриялық медиана нүктелер жиынтығының жиынтықтағы нүктелерге дейінгі арақашықтықтарының қосындысын азайту нүктесі; ол бірөлшемді медиананы жалпылайды және екі жағынан да зерттелген мекеменің орналасқан жері және сенімді статистика. Жазықтықтағы төрт нүктенің жиынтығы үшін геометриялық медиана Радон нүктесімен сәйкес келеді.

Бөлуге арналған тағы бір жалпылау р жиынтықтар берілген Хельге Тверберг  (1966 ) және қазір ретінде белгілі Тверберг теоремасы. Онда кез-келген жиынтығы үшін айтылады

${ displaystyle (d + 1) (r-1) +1 }$

евклидтік ұпай г.- кеңістік, онда бөлім бар р дөңес корпустары кем дегенде бір ортақ нүктеде қиылысатын ішкі жиындар.

Каратеодори теоремасы кейбір нүктелер жиынтығының дөңес корпусындағы кез-келген нүкте ең көп дегенде ішкі жиынның дөңес корпусында болатындығын айтады г. + 1 ұпай; яғни берілген нүкте синглтон болатын Радон бөлімінің бөлігі болып табылады. Каратеодори теоремасының бір дәлелі бір нүктені ең көбіне дейін жою үшін Радон теоремасының дәлелі сияқты сызықтық теңдеулер жүйелерінің шешімдерін зерттеу әдісін қолданады. г. + 1 қалды.

Радон теоремасына қатысты тұжырымдамалар да қарастырылды дөңес геометрия, жанұядағы кез-келген екі жиынның қиылысы отбасында қалатын қасиеттері бар ақырлы жиындардың отбасылары және бос жиын және барлық жиынтықтардың бірігуі отбасына тиесілі. Бұл жалпы контексте жиынтықтың дөңес корпусы S қамтитын отбасы мүшелерінің қиылысы болып табылады S, ал бос орынның радон саны ең кіші р кез келген р нүктелерінде дөңес корпустары қиылысатын екі жиын бар. Сол сияқты Хелли санын анықтауға болады сағ және Каратеодори нөмірі в Евклид кеңістігіндегі дөңес жиынтықтар үшін олардың анықтамаларына ұқсас және бұл сандардың теңсіздіктерді қанағаттандыратындығын көрсетуге болады сағ < р ≤ ш + 1.^[7]

Ерікті түрде бағытталмаған граф, дөңес жиынды әрқайсысын қамтитын шыңдар жиыны ретінде анықтауға болады индукцияланған жол жиынтықтағы жұп шыңдарды қосу. Осы анықтамамен графиктегі ω + 1 шыңдарының кез-келген жиынтығын дөңес қабықтары қиылысатын екі ішкі жиынға бөлуге болады, ал ω + 1 - бұл мүмкін болатын ең аз сан, мұндағы ω клик нөмірі берілген графиктің.^[8] Қатысты нәтижелер үшін ең қысқа жолдар орнына индукцияланған жолдар қараңыз Чепой (1986) және Bandelt & Pesch (1989).

Ескертулер

Әдебиеттер тізімі

• Байможи, Е. Г .; Барани, И. (1979), «Борсук пен Радон теоремасын жалпы қорыту», Acta Mathematica Hungarica, 34 (3–4): 347–350, дои:10.1007 / BF01896131.
• Банделт, Х.-Дж .; Пеш, Э. (1989), «Хелли графикасына арналған радондық теорема», Archiv der Mathematik, 52 (1): 95–98, дои:10.1007 / BF01197978.
• Чепой, В. Д. (1986), «Үшбұрышты графиктердегі d-төмпешіктің кейбір қасиеттері», Мат Шығарылды. (орыс тілінде), 87: 164–177. Келтірілгендей Bandelt & Pesch (1989).
• Кларксон, Кеннет Л.; Эппштейн, Дэвид; Миллер, Гари Л.; Тұрақты, Карл; Тэн, Шан-Хуа (1996), «Радон нүктелерімен орталық нүктелерді жуықтау» (PDF), Халықаралық есептеу геометриясы және қолданбалы журналы, 6 (3): 357–377, дои:10.1142 / s021819599600023x, МЫРЗА  1409651.
• Данцер, Л .; Грюнбаум, Б.; Кли, В. (1963), «Хелли теоремасы және оның туыстары», Дөңес, Proc. Симптом. Таза математика., 7, Американдық математикалық қоғам, 101–179 б.
• Дючет, Пьер (1987), «Дөңес жиынтықтар графиктерде. II. Минималды жол дөңес», Комбинаторлық теория журналы, А сериясы, 44 (3): 307–316, дои:10.1016/0095-8956(88)90039-1. Келтірілгендей Bandelt & Pesch (1989).
• Экхоф, Дж. (1993), «Хелли, Радон және Каратеодори типтес теоремалар», Дөңес геометрия туралы анықтама, A, B, Амстердам: Солтүстік-Голландия, 389-448 бб.
• Кей, Дэвид С .; Вомбл, Евгений В. (1971), «Каратеодори, Хелли және Радон сандарының арасындағы аксиоматикалық дөңес теория және қатынастар», Тынық мұхит журналы, 38 (2): 471–485, дои: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, die einen gemeinsamen Punkt enthalten», Mathematische Annalen, 83 (1–2): 113–115, дои:10.1007 / BF01464231.
• Тверберг, Х. (1966), «Радон теоремасын қорыту» (PDF), Лондон математикалық қоғамының журналы, 41: 123–128, дои:10.1112 / jlms / s1-41.1.123.