Momentkurve

Momentkurven er en algebraisk kurve i d - dimensionelt euklidisk rum givet af et sæt punkter med kartesiske koordinater

[1] [2] .

På det euklidiske plan er momentkurven en parabel , og i tredimensionelt rum er den en snoet kubisk kurve . Dens lukning i det projektive rum er en rationel normalkurve .

Momentkurver bruges i nogle anvendelser af kombinatorisk geometri , såsom cykliske polyedre , problemet "ingen tre punkter på samme linje" og det geometriske bevis for det kromatiske antal Kneser-grafer .

Egenskaber

Ethvert hyperplan har højst d -punkter til fælles med en kurve. Hvis hyperplanet har nøjagtigt d punkter til fælles med kurven, så skærer kurven hyperplanet ved hvert sådant punkt (dvs. rører ikke). Således er ethvert endeligt sæt punkter på momentkurven i en generel lineær position [3] [4] [5] .

Ansøgninger

Det konvekse skrog af ethvert endeligt sæt punkter på momentkurven er et cyklisk polyeder [6] [7] [4] . Cykliske polyedre har det største antal flader for et givet antal hjørner, og i dimensioner fire og derover har polyedre den egenskab, at deres kanter danner en komplet graf . Mere strengt er de adjacency polytoper , hvilket betyder, at ethvert sæt af højst d /2 hjørner af en polytop danner en af ​​dens flader. Sættet af punkter på momentkurven inkarnerer også det maksimalt mulige antal simplicer, blandt alle mulige Delaunay-trianguleringer af sæt af n punkter i et d -dimensionelt rum [8] .

På det euklidiske plan kan ethvert målbart domæne opdeles i fire lige store (i mål) delmængder (ved sandwich-sætningen ). På samme måde, men mere komplekst, kan ethvert målbart sæt i tredimensionelt rum opdeles i otte lige store (i mål) delmængder af tre planer. Dette resultat generaliserer dog ikke til fem eller flere dimensioner, da momentkurven giver et eksempel på mængder, der ikke kan dekomponeres i 2 d delmængder af d hyperplaner. Især i et femdimensionelt rum kan et sæt af fem hyperplaner opdele momentkurven i højst 26 segmenter. Det vides ikke, om det altid er muligt at opdele 4D momentkurven i 16 lige store dele af fem hyperplaner, men det er muligt at opdele 16 punkter på 4D momentkurven i 16 orthanter af et sæt af fire hyperplaner [9] [10 ] .

Konstruktionen baseret på momentkurven kan også bruges til at bevise Gales lemma, ifølge hvilket, for alle positive k og d , 2 k  +  d punkter kan placeres på en d - dimensional kugle, således at enhver åben halvkugle indeholder mindst k point. Dette lemma kan igen bruges til at beregne det kromatiske antal Kneser-grafer , et problem som Laszlo Lovas løste på en anden måde [11] [12] .

Momentkurven bruges også til grafvisualisering for at vise, at alle grafer med n toppunkter kan tegnes med toppunkter på et tredimensionelt heltalsgitter med sidelængde O( n ) uden krydsende kanter. Hovedideen er at vælge et primtal p større end n og placere grafens toppunkter i i punktet med koordinaterne

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

Så kan flyet kun skære kurven ved tre punkter. Da to skærende kanter skal have fire spidser på samme plan, kan dette ikke ske. En lignende konstruktion bruger kurven for momenter modulo et primtal, men i todimensionelt rum, og ikke i tredimensionelt, hvilket giver en lineær grænse for antallet af punkter for problemet "ingen tre punkter på en ret linje" . [fjorten]

Noter

  1. ↑ Matousek, 2002 , s. 97, Definition 5.4.1.
  2. ↑ Matousek, 2003 , s. 17, Definition 1.6.3.
  3. ↑ Edelsbrunner, 1987 , s. 100.
  4. ↑ 1 2 Matousek, 2002 , s. 97, Lemma 5.4.2.
  5. ↑ Matousek, 2003 , s. 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. ↑ Matousek, 2003 , s. 50-51.
  11. ↑ Matousek, 2003 , s. 64–67, afsnit 3.5, Gale's Lemma og Schreivers sætning.
  12. ↑ Bárány, 1978 , s. 325–326, Brugen af ​​Gales lemma til farveproblemet.
  13. ↑ Cohen, Eades, Lin, Ruskey, 1997 .
  14. ↑ Roth ( 1951 ) tilskriver Erdős opgaven .

Litteratur