Momentová křivka

Momentová křivka je algebraická křivka v d - rozměrném euklidovském prostoru daná množinou bodů s kartézskými souřadnicemi

[1] [2] .

Na euklidovské rovině je momentová křivka parabola a v trojrozměrném prostoru je to zkroucená krychlová křivka . Jeho uzavření v projektivním prostoru je racionální normální křivkou .

Momentové křivky se používají v některých aplikacích kombinatorické geometrie , jako jsou cyklické polyhedra , problém „žádné tři body na stejné lince“ geometrický důkaz chromatického počtu Kneserových grafů .

Vlastnosti

Libovolná nadrovina má s křivkou společných nejvýše d bodů. Pokud má nadrovina s křivkou společných přesně d bodů, pak křivka protíná nadrovinu v každém takovém bodě (tj. nedotýká se). Jakákoli konečná množina bodů na momentové křivce je tedy v obecné lineární poloze [3] [4] [5] .

Aplikace

Konvexní obal libovolné konečné množiny bodů na momentové křivce je cyklický mnohostěn [6] [7] [4] . Cyklické mnohostěny mají největší počet ploch pro daný počet vrcholů a v dimenzích čtyři a výše mají mnohostěny tu vlastnost, že jejich hrany tvoří úplný graf . Přesněji řečeno, jsou to sousedící polytopy , což znamená, že jakákoliv množina nejvýše d /2 vrcholů polytopu tvoří jednu z jeho ploch. Množina bodů na momentové křivce také ztělesňuje maximální možný počet zjednodušení, , mezi všemi možnými Delaunayovými triangulacemi množin n bodů v d - rozměrném prostoru [8] .

Na euklidovské rovině lze jakoukoli měřitelnou doménu rozdělit na čtyři stejné (v míře) podmnožiny (pomocí sendvičové věty ). Podobně, ale komplexněji, jakákoliv měřitelná množina v trojrozměrném prostoru může být rozdělena do osmi stejných (v míře) podmnožin třemi rovinami. Tento výsledek však nezobecňuje na pět nebo více dimenzí, protože momentová křivka poskytuje příklad množin, které nelze rozložit na 2 d podmnožiny pomocí d nadrovin. Konkrétně v pětirozměrném prostoru může sada pěti nadrovin rozdělit momentovou křivku na nejvýše 26 segmentů. Není známo, zda je vždy možné rozdělit 4D momentovou křivku na 16 stejných částí pěti nadrovinami, ale je možné rozdělit 16 bodů na 4D momentové křivce do 16 orthantů sady čtyř nadrovin [9] [10 ] .

Konstrukce založená na momentové křivce může být také použita k prokázání Galeova lemmatu, podle kterého lze pro libovolné kladné k a d umístit 2 k  +  d bodů na d - rozměrnou kouli tak, že každá otevřená polokoule obsahuje alespoň k body. Toto lemma lze zase použít k výpočtu chromatického počtu Kneserových grafů , což je problém, který Laszlo Lovas vyřešil jiným způsobem [11] [12] .

Momentová křivka se také používá pro vizualizaci grafu , aby se ukázalo, že všechny grafy s n vrcholy lze nakreslit s vrcholy na trojrozměrné celočíselné mřížce s délkou strany O( n ) bez křížení hran. Hlavní myšlenkou je vybrat prvočíslo p větší než n a umístit vrcholy i grafu do bodu se souřadnicemi

( i , i 2  mod  p , i 3  mod  p ) [13] .

Pak může rovina protínat křivku pouze ve třech bodech. Protože dvě protínající se hrany musí mít čtyři vrcholy ve stejné rovině, nemůže se to stát. Podobná konstrukce používá křivku momentů modulo prvočíslo, ale ve dvourozměrném prostoru, a ne v trojrozměrném, což dává lineární limit počtu bodů pro problém „žádné tři body na jedné přímce“ . [čtrnáct]

Poznámky

  1. ↑ Matoušek, 2002 , str. 97, definice 5.4.1.
  2. ↑ Matoušek, 2003 , str. 17, Definice 1.6.3.
  3. ↑ Edelsbrunner, 1987 , s. 100.
  4. ↑ 1 2 Matoušek, 2002 , str. 97, Lemma 5.4.2.
  5. ↑ Matoušek, 2003 , str. 17, Lemma 1.6.4.
  6. ↑ Gale, 1963 .
  7. ↑ Edelsbrunner, 1987 , s. 101.
  8. ↑ Amenta, Attali, Devillers, 2007 .
  9. ↑ Edelsbrunner, 1987 , s. 70–79.
  10. ↑ Matoušek, 2003 , str. 50–51.
  11. ↑ Matoušek, 2003 , str. 64–67, oddíl 3.5, Galeovo lemma a Schreiverova věta.
  12. ↑ Bárány, 1978 , s. 325–326, Použití Galeova lemmatu pro problém barvení.
  13. ↑ Cohen, Eades, Lin, Ruskey, 1997 .
  14. ↑ Roth ( 1951 ) připisuje úkol Erdősovi .

Literatura