Momentkurva

Inom geometri är momentkurvan en algebraisk kurva i d -dimensionell euklidisk rymd som ges av uppsättningen punkter med kartesiska koordinater av formen

$\left(x,x^{2},x^{3},\dots,x^{d}\right).$

I det euklidiska planet är momentkurvan en parabel , och i tredimensionellt utrymme är den en vriden kubik . Dess stängning i projektivt utrymme är den rationella normalkurvan .

Momentkurvor har använts för flera tillämpningar inom diskret geometri , inklusive cykliska polytoper , problemet utan tre i rad, och ett geometriskt bevis på det kromatiska antalet Kneser -grafer .

Egenskaper

Varje hyperplan skär momentkurvan i en ändlig uppsättning av högst d punkter. Om ett hyperplan skär kurvan i exakt d punkter, så korsar kurvan hyperplanet vid varje skärningspunkt. Således är varje ändlig punkt inställd på momentkurvan i allmänt linjär position .

Ansökningar

Det konvexa skrovet av en ändlig uppsättning punkter på momentkurvan är en cyklisk polytop . Cykliska polytoper har största möjliga antal ytor för ett givet antal hörn, och i dimensioner fyra eller fler har egenskapen att deras kanter bildar en komplett graf . Mer starkt, de är grannpolytoper , vilket betyder att varje uppsättning av högst d /2 hörn av polytopen bildar en av dess ytor. Uppsättningar av punkter på momentkurvan realiserar också det maximalt möjliga antalet förenklingar, ${\displaystyle \Omega (n^{\lceil d/2\rceil })} ,$ bland alla möjliga Delaunay-trianguleringar av uppsättningar av n punkter i d- dimensioner.

I det euklidiska planet är det möjligt att dela upp vilken yta eller åtgärd som helst i fyra lika stora delmängder, med hjälp av skinksmörgåssatsen . På liknande sätt men mer komplicerat kan varje volym eller mått i tre dimensioner delas upp i åtta lika stora delmängder med tre plan. Detta resultat generaliserar dock inte till fem eller fler dimensioner, eftersom momentkurvan ger exempel på mängder som inte kan delas upp i 2 ^d delmängder av d hyperplan. Speciellt i fem dimensioner kan uppsättningar av fem hyperplan dela upp segment av momentkurvan i högst 26 delar. Det är inte känt om fyrdimensionella partitioner i 16 lika delmängder av fyra hyperplan alltid är möjliga, men det är möjligt att dela upp 16 punkter på den fyrdimensionella momentkurvan i de 16 orthanterna i en uppsättning av fyra hyperplan.

En konstruktion baserad på momentkurvan kan användas för att bevisa ett lemma av Gale, enligt vilket det för alla positiva heltal k och d är möjligt att placera 2 k + d punkter på en d -dimensionell sfär på ett sådant sätt att varje öppen halvklot innehåller minst k punkter. Detta lemma kan i sin tur användas för att beräkna det kromatiska antalet av Kneser-graferna , ett problem som först löstes på ett annat sätt av László Lovász .

Momentkurvan har också använts vid grafritning för att visa att alla n -vertexgrafer kan ritas med sina hörn i ett tredimensionellt heltalsrutnät med sidolängden O( n ) och utan att två kanter korsar. Huvudidén är att välja ett primtal p som är större än n och att placera grafens vertex i vid koordinater

( i , i ² mod p , i ³ mod p ).

Då kan ett plan bara korsa kurvan vid tre positioner. Eftersom två korsande kanter måste ha fyra hörn i samma plan kan detta aldrig hända. En liknande konstruktion som använder momentkurvan modulo ett primtal, men i två dimensioner snarare än tre, ger en linjär gräns för problemet utan tre i rad .

Anteckningar

•   Amenta, Nina ; Attali, Dominique; Devillers, Olivier (2007), "Complexity of Delaunay triangulation for points on lower-dimensional polyhedra", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms , New York: ACM, s. 1106–1113, MR 2485262 .
•   Bárány, I. (1978), "A short proof of Knesers conjecture", Journal of Combinatorial Theory , Series A, 25 (3): 325–326, doi : 10.1016/0097-3165(78)90023-7 , MR 620511 .
•   Cohen, RF; Eades, P. ; Lin, Tao; Ruskey, F. (1997), "Tredimensionell grafritning", Algorithmica , 17 (2): 199–208, doi : 10.1007/BF02522826 , MR 1425733 .
•    Edelsbrunner, Herbert (1987), Algorithms in Combinatorial Geometry , EATCS Monographs on Theoretical Computer Science, vol. 10, Berlin: Springer-Verlag, ISBN 3-540-13722-X , MR 0904271 .
•   Gale, David (1963), "Neighborly and cyclic polytopes", i Klee, Victor (red.), Convexity, Seattle, 1961 , Symposia in Pure Mathematics, vol. 7, Providence, RI: American Mathematical Society, s. 225–232, MR 0152944 .
•   Matoušek, Jiří (2002), Lectures on Discret Geometry , Graduate Texts in Mathematics , vol. 212, Springer-Verlag, ISBN 978-0-387-95373-1 .
•   Matoušek, Jiří (2003), Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry , Universitext, Springer, ISBN 978-3-540-00362-5 .
• Roth, KF (1951), "On a problem of Heilbronn", Journal of the London Mathematical Society , 26 (3): 198–204, doi : 10.1112/jlms/s1-26.3.198 .