Moment curve
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
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 affine general 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
- ^ Matoušek (2002), Definition 5.4.1, p. 97; Matoušek (2003), Definition 1.6.3, p. 17.
- ^ Edelsbrunner (1987), p. 100; Matoušek (2002), Lemma 5.4.2, p. 97; Matoušek (2003), Lemma 1.6.4, p. 17.
- ^ Gale (1963); Edelsbrunner (1987), p. 101; Matoušek (2002), Lemma 5.4.2, p. 97.
- ^ Amenta, Attali & Devillers (2007).
- ^ Edelsbrunner (1987), pp. 70–79; Matoušek (2003), pp. 50–51.
- ^ 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 Bárány (1978).
- ^ Cohen et al. (1997).
- ^ Credited by Roth (1951) to Paul Erdős.
References
- 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, pp. 1106–1113, MR 2485262.
- Bárány, I. (1978), "A short proof of Kneser's conjecture", Journal of Combinatorial Theory, Series A, 25 (3): 325–326, doi:10.1016/0097-3165(78)90023-7, MR 0514626.
- Cohen, R. F.; Eades, P.; Lin, Tao; Ruskey, F. (1997), "Three-dimensional graph drawing", 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", in Klee, Victor (ed.), Convexity, Seattle, 1961, Symposia in Pure Mathematics, vol. 7, Providence, R.I.: American Mathematical Society, pp. 225–232, MR 0152944.
- Matoušek, Jiří (2002), Lectures on Discrete 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, K. F. (1951), "On a problem of Heilbronn", Journal of the London Mathematical Society, 26 (3): 198–204, doi:10.1112/jlms/s1-26.3.198.