Pillanat görbe

A nyomatékgörbe egy algebrai görbe d - dimenziós euklideszi térben , amelyet derékszögű koordinátákkal rendelkező pontok halmaza ad meg.

[1] [2] .

Az euklideszi síkon a nyomatékgörbe egy parabola , háromdimenziós térben pedig egy csavart köbös görbe . Zártsága projektív térben racionális normálgörbe .

A momentumgörbéket a kombinatorikus geometria egyes alkalmazásaiban használják , például a ciklikus poliédereknél , a "nincs három pont ugyanazon a vonalon" probléma és a Kneser-gráfok kromatikus számának geometriai bizonyítása .

Tulajdonságok

Bármely hipersíknak legfeljebb d pontja van egy görbével. Ha a hipersíknak pontosan d pontja van a görbével, akkor a görbe minden ilyen pontban metszi a hipersíkot (azaz nem érinti). Így a nyomatékgörbe bármely véges ponthalmaza általános lineáris helyzetben van [3] [4] [5] .

Alkalmazások

A nyomatékgörbe bármely véges ponthalmazának konvex burka egy ciklikus poliéder [6] [7] [4] . A ciklikus poliédereknek van a legtöbb lapja adott számú csúcshoz, és a négyes és nagyobb dimenziókban a poliédereknek az a tulajdonsága, hogy éleik teljes gráfot alkotnak . Pontosabban, szomszédsági politópokról van szó, ami azt jelenti, hogy egy politóp legfeljebb d /2 csúcsából álló halmaz alkotja annak egyik lapját. A nyomatékgörbe ponthalmaza egy d - dimenziós térben n pontból álló halmazok összes lehetséges Delaunay-háromszögelése között a lehető legnagyobb számú egyszerűséget is megtestesíti [8] .

Az euklideszi síkon bármely mérhető tartomány négy egyenlő (mértékben) részhalmazra osztható (a szendvicstétellel ). Hasonlóan, de összetettebben, bármely háromdimenziós térben mérhető halmaz felosztható nyolc egyenlő (mértékben) részhalmazra három síkkal. Ez az eredmény azonban nem általánosít öt vagy több dimenzióra, mivel a nyomatékgörbe olyan halmazokra ad példát, amelyeket nem lehet d hipersíkkal 2 d részhalmazokra bontani. Egy ötdimenziós térben egy öt hipersík halmaza legfeljebb 26 szegmensre oszthatja fel a nyomatékgörbét. Nem ismert, hogy mindig lehetséges-e a 4D nyomatékgörbét öt hipersíkkal 16 egyenlő részre felosztani, de a 4D nyomatékgörbe 16 pontját egy négy hipersík halmazának 16 ortánsára fel lehet osztani [9] [10 ] .

A nyomatékgörbén alapuló konstrukció felhasználható a Gale-lemmának bizonyítására is, amely szerint bármely pozitív k és d esetén 2 k  +  d pont helyezhető el egy d - dimenziós gömbön úgy, hogy bármely nyitott félgömb legalább k -t tartalmazzon. pontokat. Ez a lemma pedig felhasználható a Kneser-gráfok kromatikus számának kiszámítására , amit Lovas László másképpen oldott meg [11] [12] .

A nyomatékgörbét a gráf vizualizálására is használják annak bemutatására, hogy minden n csúcsú gráf megrajzolható csúcsokkal egy O( n ) oldalhosszú háromdimenziós egészrácson élek keresztezése nélkül. A fő ötlet az, hogy válasszunk egy n - nél nagyobb p prímszámot , és helyezzük a gráf i csúcsait a koordinátákkal rendelkező pontba.

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

Ekkor a sík csak három pontban metszi a görbét. Mivel két egymást metsző élnek négy csúcsnak kell lennie ugyanazon a síkon, ez nem fordulhat elő. Egy hasonló konstrukció egy prímszám modulo nyomatékgörbéjét használja, de kétdimenziós térben, és nem háromdimenziósban, ami lineáris korlátot ad a pontok számára a "nincs három pont egy egyenesen" probléma . [tizennégy]

Jegyzetek

  1. ↑ Matousek, 2002 , p. 97, Meghatározás 5.4.1.
  2. ↑ Matousek, 2003 , p. 17. Meghatározás 1.6.3.
  3. ↑ Edelsbrunner, 1987 , p. 100.
  4. ↑ 1 2 Matousek, 2002 , p. 97, Lemma 5.4.2.
  5. ↑ Matousek, 2003 , p. 17, Lemma 1.6.4.
  6. ↑ Gale, 1963 .
  7. ↑ Edelsbrunner, 1987 , p. 101.
  8. ↑ Amenta, Attali, Devillers, 2007 .
  9. ↑ Edelsbrunner, 1987 , p. 70–79.
  10. ↑ Matousek, 2003 , p. 50–51.
  11. ↑ Matousek, 2003 , p. 64–67, 3.5. szakasz, Gale-lemma és Schreiver-tétel.
  12. ↑ Bárány, 1978 , p. 325–326, Gale-lemma használata a színezési problémára.
  13. ↑ Cohen, Eades, Lin, Ruskey, 1997 .
  14. ↑ Roth ( 1951 ) Erdősnek tulajdonítja a feladatot .

Irodalom