Radonova věta - Radons theorem - Wikipedia

v geometrie, Radonova věta na konvexní sady, publikováno Johann Radon v roce 1921 uvádí, že jakýkoli soubor d + 2 body R^d může být rozdělené do dvou sad, jejichž konvexní trupy protínají. Bod v průsečíku těchto konvexních trupů se nazývá a Radonový bod sady.

Například v případě d = 2, libovolná sada čtyř bodů v Euklidovské letadlo lze rozdělit jedním ze dvou způsobů. Může tvořit trojitý a singleton, kde konvexní trup trojitého (trojúhelník) obsahuje singleton; alternativně může tvořit dva páry bodů, které tvoří koncové body dvou protínajících se úsečky.

Důkaz a konstrukce

Dvě sady čtyř bodů v rovině (vrcholy čtverce a rovnostranný trojúhelník s těžištěm), multiplikátory řešící systém tří lineárních rovnic pro tyto body a radonové oddíly vytvořené oddělením bodů kladnými multiplikátory od body se zápornými multiplikátory.

Zvažte jakoukoli sadu ${ displaystyle X = {x_ {1}, x_ {2}, dots, x_ {d + 2} } podmnožina mathbf {R} ^ {d}}$ z d + 2 body d-rozměrný prostor. Pak existuje sada multiplikátorů A₁, ..., A_d + 2, ne všechny jsou nula, řešení soustava lineárních rovnic

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

protože tam jsou d + 2 neznámé (multiplikátory), ale pouze d + 1 rovnice, které musí splňovat (jedna pro každou souřadnici bodů, spolu s konečnou rovnicí vyžadující, aby součet multiplikátorů byl nulový). Opravte nějaké konkrétní nenulové řešení A₁, ..., A_d + 2. Nechat ${ displaystyle I subseteq X}$ být množinou bodů s kladnými multiplikátory a nechat ${ displaystyle J = X setminus I}$ být množina bodů s multiplikátory, které jsou záporné nebo nulové. Pak ${ displaystyle I}$ a ${ displaystyle J}$ vytvořte požadované rozdělení bodů do dvou podmnožin s protínajícími se konvexními trupy.

Konvexní trupy ${ displaystyle I}$ a ${ displaystyle J}$ musí protínat, protože oba obsahují bod

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

kde

${ displaystyle A = součet _ {i v I} a_ {i} = - součet _ {j v J} a_ {j}.}$

Levá strana vzorce pro ${ displaystyle p}$ vyjadřuje tento bod jako a konvexní kombinace bodů v ${ displaystyle I}$a pravá strana to vyjadřuje jako konvexní kombinaci bodů v ${ displaystyle J}$. Proto, ${ displaystyle p}$ patří k oběma konvexním trupům, což vyplňuje důkaz.

Tato důkazní metoda umožňuje efektivní konstrukci radonového bodu po určitou dobu polynomiální v dimenzi pomocí Gaussova eliminace nebo jiné efektivní algoritmy k řešení systému rovnic pro multiplikátory.^[1]

Topologická věta o radonu

A topologické zobecnění Radonovy věty uvádí, že pokud ƒ existuje spojitá funkce z (d + 1) -dimenzionální simplexní na d-dimenzionální prostor, simplex má potom dvě nesouvislé tváře, jejichž obrázky pod ƒ nejsou nesouvislé.^[2] Samotnou Radonovu větu lze interpretovat jako speciální případ, ve kterém je ƒ jedinečný afinní mapa který vezme vrcholy simplexu na danou množinu d + 2 body d-rozměrný prostor.

Obecněji, pokud K. je jakýkoli (d + 1) -dimenzionální kompaktní konvexní množina a ƒ je jakákoli spojitá funkce od K. na d-dimenzionální prostor, pak existuje lineární funkce G tak, že někdy místo G dosáhne své maximální hodnoty a nějakého dalšího bodu, kde G dosáhne své minimální hodnoty, jsou mapovány o ƒ do stejného bodu. V případě, že K. je simplex, dvě simplexní plochy tvořené maximem a minimem bodů G pak musí být dvě nesouvislé tváře, jejichž obrazy mají neprázdný průnik. Stejné obecné prohlášení, když se použije na a hypersféra místo simplexu dává Borsuk – Ulamova věta, že ƒ musí mapovat dva protilehlé body koule do stejného bodu.^[2]

Aplikace

Radonový bod libovolných čtyř bodů v rovině je jejich geometrický medián, bod, který minimalizuje součet vzdáleností k ostatním bodům.^[3][4]

Radonova věta tvoří klíčový krok standardního důkazu Hellyho věta na křižovatkách konvexních množin;^[5] tento důkaz byl motivací pro Radonův původní objev Radonovy věty.

Radonovu větu lze také použít k výpočtu VC rozměr z d-dimenzionální body vzhledem k lineárním oddělením. Existují sady d +1 body (například body obyčejného simplexu), takže každé dvě neprázdné podmnožiny lze od sebe oddělit nadrovinou. Bez ohledu na to, z jaké sady d Jsou dány + 2 body, dvě podmnožiny radonového oddílu nelze lineárně oddělit. Proto je rozměr VC tohoto systému přesně d + 1.^[6]

A randomizovaný algoritmus který opakovaně nahrazuje sady d + 2 body podle jejich radonového bodu lze použít k výpočtu přiblížení do a centrální bod libovolné množiny bodů v čase, který je polynomický jak v počtu bodů, tak v dimenzi.^[1]

Související pojmy

Radonový bod tří bodů v jednorozměrném prostoru je jen jejich medián. The geometrický medián množiny bodů je bod minimalizující součet vzdáleností k bodům v množině; zobecňuje jednorozměrný medián a byl studován jak z pohledu umístění zařízení a robustní statistiky. U sad čtyř bodů v rovině se geometrický medián shoduje s radonovým bodem.

Další zobecnění pro oddíl do r sady byly dány Helge Tverberg  (1966 ) a je nyní známý jako Tverbergova věta. Uvádí se v něm, že pro jakoukoli sadu

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

body v euklidovštině d-prostor, do kterého je oddíl r podmnožiny, jejichž konvexní trupy se protínají alespoň v jednom společném bodě.

Carathéodoryova věta uvádí, že jakýkoli bod v konvexním trupu některé sady bodů je také v konvexním trupu podmnožiny nejvýše d +1 bod; to znamená, že daný bod je součástí radonového oddílu, ve kterém je singleton. Jeden důkaz Carathéodoryho věty používá techniku ​​zkoumání řešení systémů lineárních rovnic, podobně jako důkaz Radonovy věty, k eliminaci jednoho bodu po druhém, maximálně d + 1 zůstávají.

Byly vzaty v úvahu i koncepty související s Radonovou větou konvexní geometrie, rodiny konečných množin s vlastnostmi, že průnik dvou libovolných množin v rodině zůstane v rodině a že prázdná sada a spojení všech souborů patří rodině. V tomto obecnějším kontextu je konvexní trup množiny S je průsečík členů rodiny, které obsahují Sa radonové číslo mezery je nejmenší r takový, že jakýkoli r body mají dvě podmnožiny, jejichž konvexní trupy se protínají. Podobně lze definovat číslo Helly h a číslo Carathéodory C analogicky k jejich definicím pro konvexní množiny v euklidovských prostorech a je možné ukázat, že tato čísla uspokojují nerovnosti h < r ≤ ch + 1.^[7]

Svévolně neorientovaný graf lze definovat konvexní množinu jako sadu vrcholů, která zahrnuje všechny indukovaný cesta připojení dvojice vrcholů v sadě. S touto definicí lze každou sadu vrcholů ω + 1 v grafu rozdělit na dvě podmnožiny, jejichž konvexní trupy se protínají, a ω + 1 je minimální počet, pro který je to možné, kde ω je číslo kliky daného grafu.^[8] Související výsledky zahrnují nejkratší cesty místo indukovaných cest viz Chepoi (1986) a Bandelt & Pesch (1989).

Poznámky

Reference

• Bajmóczy, E. G .; Bárány, I. (1979), „Společné zobecnění Borsukovy a Radonovy věty“, Acta Mathematica Hungarica, 34 (3–4): 347–350, doi:10.1007 / BF01896131.
• Bandelt, H.-J .; Pesch, E. (1989), „Radonova věta pro Hellyho grafy“, Archiv der Mathematik, 52 (1): 95–98, doi:10.1007 / BF01197978.
• Chepoi, V. D. (1986), „Některé vlastnosti d-konvexity v trojúhelníkových grafech“, Rohož. Issled. (v Rusku), 87: 164–177. Jak uvádí Bandelt & Pesch (1989).
• Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua (1996), "Přibližování středových bodů s iterovanými radonovými body" (PDF), International Journal of Computational Geometry & Applications, 6 (3): 357–377, doi:10,1142 / s021819599600023x, PAN  1409651.
• Danzer, L .; Grünbaum, B.; Klee, V. (1963), „Hellyho věta a její příbuzní“, Konvexnost, Proc. Symp. Čistá matematika., 7, Americká matematická společnost, str. 101–179.
• Duchet, Pierre (1987), "Konvexní množiny v grafech. II. Minimální konvexnost dráhy", Journal of Combinatorial Theory, Series A, 44 (3): 307–316, doi:10.1016/0095-8956(88)90039-1. Jak uvádí Bandelt & Pesch (1989).
• Eckhoff, J. (1993), „Věty typu Helly, Radon a Carathéodory“, Příručka konvexní geometrie, A, B, Amsterdam: Severní Holandsko, s. 389–448.
• Kay, David C .; Womble, Eugene W. (1971), „Axiomatická teorie konvexity a vztahy mezi čísly Carathéodory, Helly a Radon“, Pacific Journal of Mathematics, 38 (2): 471–485, doi:10,2140 / pjm.1971,38.471, PAN  0310766.
• Matoušek, J. (2002), „1.3 Radonova lemma a Hellyho věta“, Přednášky o diskrétní geometrii, Postgraduální texty z matematiky, 212, Springer-Verlag, str. 9–12, ISBN  978-0-387-95373-1.
• Matoušek, J. (2003), „5.1 Věty o nevstupnosti: úvod“, Použití věty Borsuk – Ulam: Přednášky o topologických metodách v kombinatorice a geometrii, Springer-Verlag, str. 88–92.
• Radon, J. (1921), „Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten“, Mathematische Annalen, 83 (1–2): 113–115, doi:10.1007 / BF01464231.
• Tverberg, H. (1966), „Zobecnění Radonovy věty“ (PDF), Journal of the London Mathematical Society, 41: 123–128, doi:10.1112 / jlms / s1-41.1.123.