- Properties
- Applications
- Notes
- References
In geometry, the moment curve is an algebraic curve in d-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form
[1]
In the Euclidean plane, the moment curve is a parabola, and in three-dimensional space it is a twisted cubic. Its closure in projective space is the rational normal curve.
Moment curves have been used for several applications in discrete geometry including cyclic polytopes, the no-three-in-line problem, and a geometric proof of the chromatic number of Kneser graphs.
Properties
Every hyperplane intersects the moment curve in a finite set of at most d points. If a hyperplane intersects the curve in exactly d points, then the curve crosses the hyperplane at each intersection point. Thus, every finite point set on the moment curve is in general linear position.[2]
Applications
The convex hull of any finite set of points on the moment curve is a cyclic polytope.[3] Cyclic polytopes have the largest possible number of faces for a given number of vertices, and in dimensions four or more have the property that their edges form a complete graph. More strongly, they are neighborly polytopes, meaning that each set of at most d/2 vertices of the polytope forms one of its faces. Sets of points on the moment curve also realize the maximum possible number of simplices, 
, among all possible Delaunay triangulations of sets of n points in d dimensions.[4]
In the Euclidean plane, it is possible to divide any area or measure into four equal subsets, using the ham sandwich theorem. Similarly but more complicatedly, any volume or measure in three dimensions may be partitioned into eight equal subsets by three planes. However, this result does not generalize to five or more dimensions, as the moment curve provides examples of sets that cannot be partitioned into 2d subsets by d hyperplanes. In particular, in five dimensions, sets of five hyperplanes can partition segments of the moment curve into at most 26 pieces. It is not known whether four-dimensional partitions into 16 equal subsets by four hyperplanes are always possible, but it is possible to partition 16 points on the four-dimensional moment curve into the 16 orthants of a set of four hyperplanes.[5]
A construction based on the moment curve can be used to prove a lemma of Gale, according to which, for any positive integers k and d, it is possible to place 2k + d points on a d-dimensional sphere in such a way that every open hemisphere contains at least k points. This lemma, in turn, can be used to calculate the chromatic number of the Kneser graphs, a problem first solved in a different way by László Lovász.[6]
The moment curve has also been used in graph drawing, to show that all n-vertex graphs may be drawn with their vertices in a three-dimensional integer grid of side length O(n) and with no two edges crossing. The main idea is to choose a prime number p larger than n and to place vertex i of the graph at coordinates
(i, i 2 mod p, i 3 mod p).[7]
Then a plane can only cross the curve at three positions. Since two crossing edges must have four vertices in the same plane, this can never happen.
A similar construction using the moment curve modulo a prime number, but in two dimensions rather than three, provides a linear bound for the no-three-in-line problem.[8]
Notes
2. ^{{harvtxt|Edelsbrunner|1987}}, p. 100; {{harvtxt|Matoušek|2002}}, Lemma 5.4.2, p. 97; {{harvtxt|Matoušek|2003}}, Lemma 1.6.4, p. 17.
3. ^{{harvtxt|Gale|1963}}; {{harvtxt|Edelsbrunner|1987}}, p. 101; {{harvtxt|Matoušek|2002}}, Lemma 5.4.2, p. 97.
4. ^{{harvtxt|Amenta|Attali|Devillers|2007}}.
5. ^{{harvtxt|Edelsbrunner|1987}}, pp. 70–79; {{harvtxt|Matoušek|2003}}, pp. 50–51.
6. ^{{harvtxt|Matoušek|2003}}, Section 3.5, Gale's Lemma and Schrijver's Theorem, pp. 64–67. The use of Gale's lemma for the coloring problem is due to {{harvtxt|Bárány|1978}}.
7. ^{{harvtxt|Cohen|Eades|Lin|Ruskey|1997}}.
8. ^Credited by {{harvtxt|Roth|1951}} to Paul Erdős.
References
{{refbegin|colwidth=30em}}- {{citation
| last1 = Amenta | first1 = Nina | author1-link = Nina Amenta
| last2 = Attali | first2 = Dominique
| last3 = Devillers | first3 = Olivier
| contribution = Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
| location = New York
| mr = 2485262
| pages = 1106–1113
| publisher = ACM
| title = Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms
| year = 2007}}.
- {{citation
| last = Bárány | first = I. | authorlink = Imre Bárány
| doi = 10.1016/0097-3165(78)90023-7
| issue = 3
| journal = Journal of Combinatorial Theory | series = Series A
| mr = 514626
| pages = 325–326
| title = A short proof of Kneser's conjecture
| volume = 25
| year = 1978}}.
- {{citation
| last1 = Cohen | first1 = R. F.
| last2 = Eades | first2 = P. | author2-link = Peter Eades
| last3 = Lin | first3 = Tao
| last4 = Ruskey | first4 = F. | author4-link = Frank Ruskey
| doi = 10.1007/BF02522826
| issue = 2
| journal = Algorithmica
| mr = 1425733
| pages = 199–208
| title = Three-dimensional graph drawing
| volume = 17
| year = 1997}}.
- {{citation
| last = Edelsbrunner | first = Herbert | authorlink = Herbert Edelsbrunner
| isbn = 3-540-13722-X
| location = Berlin
| mr = 904271
| publisher = Springer-Verlag
| series = EATCS Monographs on Theoretical Computer Science
| title = Algorithms in Combinatorial Geometry
| volume = 10
| year = 1987}}.
- {{citation
| last = Gale | first = David | author-link = David Gale
| contribution = Neighborly and cyclic polytopes
| editor-last = Klee | editor-first = Victor | editor-link = Victor Klee
| location = Providence, R.I.
| mr = 0152944
| pages = 225–232
| publisher = American Mathematical Society
| series = Symposia in Pure Mathematics
| title = Convexity, Seattle, 1961
| volume = 7
| year = 1963}}.
- {{citation
| last = Matoušek | first = Jiří | author-link = Jiří Matoušek (mathematician)
| isbn = 978-0-387-95373-1
| publisher = Springer-Verlag
| series = Graduate Texts in Mathematics
| title = Lectures on Discrete Geometry
| volume = 212
| year = 2002}}.
- {{citation
| last = Matoušek | first = Jiří | author-link = Jiří Matoušek (mathematician)
| isbn = 978-3-540-00362-5
| publisher = Springer
| series = Universitext
| title = Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry
| year = 2003}}.
- {{citation
| last = Roth | first = K. F. | authorlink = Klaus Roth
| doi = 10.1112/jlms/s1-26.3.198
| issue = 3
| journal = Journal of the London Mathematical Society
| pages = 198–204
| title = On a problem of Heilbronn
| volume = 26
| year = 1951}}.{{refend}}
- If You Leave Me Now (album)
- If You Leave Me Now (Chicago Album)
- If You Leave Me Now (Chicago album)
- (If You Let Me Make Love To You Then) Why Can't I Touch You?
- (If You Let Me Make Love to You Then) Why Can't I Touch You?
- If You Love Me
- If You Love Me (Mint Condition song)
- If You Love Me (song)
- If You Love Someone
- If You Love Your Children
- If you miss me at the back of the bus
- If You Miss Me at the Back of the Bus
- If You Must
- If You Must (album)
- If You Must (disambiguation)
- If You Must (song)
- If You Need Me
- If You Only Knew
- If You Only Knew (disambiguation)
- If You Only Knew (film)
- If You're Gonna Do Me Wrong (Do It Right)
- If You're Gonna Walk, I'm Gonna Crawl
- If you're good at something, never do it for free
- If You're Happy & You Know It
- If You're Lucky