Curba momentului

Curba momentului este o curbă algebrică în spațiul euclidian d - dimensional dat de un set de puncte cu coordonate carteziene

Pe planul euclidian , curba momentului este o parabolă , iar în spațiul tridimensional este o curbă cubică răsucită . Închiderea sa în spațiul proiectiv este o curbă normală rațională .

Curbele de moment sunt utilizate în unele aplicații ale geometriei combinatorii , cum ar fi poliedre ciclice , problema „fără trei puncte pe aceeași linie” demonstrația geometrică a numărului cromatic al graficelor Kneser .

Proprietăți

Orice hiperplan are cel mult d puncte în comun cu o curbă. Dacă hiperplanul are exact d puncte în comun cu curba, atunci curba intersectează hiperplanul în fiecare astfel de punct (adică, nu se atinge). Astfel, orice set finit de puncte de pe curba momentului se află într-o poziție liniară generală [3] [4] [5] .

Aplicații

Corpul convex al oricărui set finit de puncte de pe curba momentului este un poliedru ciclic [6] [7] [4] . Poliedrele ciclice au cel mai mare număr de fețe pentru un număr dat de vârfuri, iar la dimensiunile patru și mai sus, poliedrele au proprietatea că muchiile lor formează un grafic complet . Mai strict, sunt politopuri de adiacență , ceea ce înseamnă că orice set de cel mult d /2 vârfuri ale unui politop formează una dintre fețele sale. Mulțimea punctelor de pe curba momentului încorporează și numărul maxim posibil de simplexe, , dintre toate triangulațiile Delaunay posibile ale mulțimilor de n puncte într-un spațiu d - dimensional [8] .

Pe planul euclidian , orice domeniu măsurabil poate fi împărțit în patru submulțimi egale (în măsură) (prin teorema sandwich ). În mod similar, dar mai complex, orice mulțime măsurabilă din spațiul tridimensional poate fi împărțită în opt subseturi egale (în măsură) de trei plane. Totuși, acest rezultat nu se generalizează la cinci sau mai multe dimensiuni, deoarece curba momentului oferă un exemplu de mulțimi care nu pot fi descompuse în 2 d submulțimi de d hiperplanuri. În special, într-un spațiu cu cinci dimensiuni, un set de cinci hiperplane poate împărți curba momentului în cel mult 26 de segmente. Nu se știe dacă este întotdeauna posibilă împărțirea curbei momentului 4D în 16 părți egale cu cinci hiperplane, dar este posibilă împărțirea a 16 puncte de pe curba momentului 4D în 16 orante dintr-un set de patru hiperplane [9] [10 ]. ] .

Construcția bazată pe curba momentului poate fi folosită și pentru a demonstra lema lui Gale, conform căreia, pentru orice k și d pozitiv, 2 k  +  d puncte pot fi plasate pe o sferă d - dimensională astfel încât orice emisferă deschisă să conțină cel puțin k puncte. Această lemă, la rândul ei, poate fi folosită pentru a calcula numărul cromatic al graficelor Kneser , problemă pe care Laszlo Lovas a rezolvat -o într-un mod diferit [11] [12] .

Curba momentului este, de asemenea, utilizată pentru vizualizarea graficului pentru a arăta că toate graficele cu n vârfuri pot fi desenate cu vârfuri pe o rețea de numere întregi tridimensionale cu lungimea laturii O( n ) fără margini de încrucișare. Ideea principală este să alegeți un număr prim p mai mare decât n și să plasați vârfurile i ale graficului în punctul cu coordonatele

Atunci planul poate intersecta curba numai în trei puncte. Deoarece două muchii care se intersectează trebuie să aibă patru vârfuri pe același plan, acest lucru nu se poate întâmpla. O construcție similară folosește curba momentelor modulo un număr prim, dar în spațiu bidimensional, și nu în tridimensional, ceea ce dă o limită liniară a numărului de puncte pentru problema „fără trei puncte pe o linie dreaptă” . [paisprezece]

Note

1. ↑ Matousek, 2002 , p. 97, Definiția 5.4.1.
2. ↑ Matousek, 2003 , p. 17, Definiția 1.6.3.
3. ↑ Edelsbrunner, 1987 , p. 100.
4. ↑ 1 2 Matousek, 2002 , p. 97, Lema 5.4.2.
5. ↑ Matousek, 2003 , p. 17, Lema 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, Secțiunea 3.5, Lema lui Gale și teorema lui Schreiver.
12. ↑ Bárány, 1978 , p. 325–326, Utilizarea lemei lui Gale pentru problema colorării.
13. ↑ Cohen, Eades, Lin, Ruskey, 1997 .
14. ↑ Roth ( 1951 ) atribuie sarcina lui Erdős .

Literatură

• Nina Amenta, Dominique Attali, Olivier Devillers. Complexitatea triangulației Delaunay pentru puncte pe poliedre de dimensiuni inferioare // Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. - New York: ACM, 2007. - S. 1106-1113. .
• Bárány I. O scurtă dovadă a conjecturei lui Kneser // Journal of Combinatorial Theory . - 1978. - T. 25 , nr. 3 . - doi : 10.1016/0097-3165(78)90023-7 .
• Cohen RF, Eades P., Lin Tao, Ruskey F. Desen grafic tridimensional // Algorithmica . - 1997. - T. 17 , nr. 2 . — S. 199–208 . - doi : 10.1007/BF02522826 .
• Herbert Edelsbrunner. Algoritmi în geometrie combinatorie. - Berlin: Springer-Verlag, 1987. - Vol. 10. - (Monografii EATCS despre informatica teoretica). — ISBN 3-540-13722-X .
• David Gale. Politopi învecinați și ciclici // Convexity, Seattle, 1961 / Victor Klee. - Providence, RI: Societatea Americană de Matematică, 1963. - V. 7. - S. 225-232. — (Simpozioane de matematică pură).
• Jiri Matousek. Prelegeri despre geometrie discretă. - Springer-Verlag, 2002. - V. 212. - ( Texte de absolvent în matematică ). — ISBN 978-0-387-95373-1 .
• Jiri Matousek. Utilizarea teoremei Borsuk-Ulam: Prelegeri despre metode topologice în combinatorică și geometrie. - Springer, 2003. - (Universitex). - ISBN 978-3-540-00362-5 .
• Roth KF Despre o problemă a lui Heilbronn // Journal of the London Mathematical Society . - 1951. - T. 26 , nr. 3 . — S. 198–204 . - doi : 10.1112/jlms/s1-26.3.198 .