The curve of moments is an algebraic curve in a d- dimensional Euclidean space defined by a set of points with Cartesian coordinates
- [1] [2] .
On the Euclidean plane , the moment curve is a parabola , and in three-dimensional space a . Its closure in the projective space is a rational normal curve .
Moment curves are used in some applications of combinatorial geometry , such as cyclic polyhedra , , and the geometric proof of the chromatic number of Kneser graphs .
Content
- 1 Properties
- 2 Applications
- 3 notes
- 4 Literature
Properties
Any hyperplane with a curve has at most d common points. If a hyperplane has exactly d common points with a curve, then the curve intersects the hyperplane at each such point (i.e., does not touch). Thus, any finite set of points on the curve of moments is in the general linear position [3] [4] [5] .
Applications
The convex hull of any finite set of points on the curve of moments is a cyclic polyhedron [6] [7] [4] . Cyclic polyhedra have the largest number of faces for a given number of vertices, and in dimensions of four and higher the polyhedra have the property that their edges form a complete graph . More strictly, they are adjacent polyhedra , which means that any set of at most d / 2 vertices of a polyhedron forms one of its faces. The set of points on the curve of moments also embodies the maximum possible number of simplexes, , among all possible Delaunay triangulations of sets of n points in a d- dimensional space [8] .
On the Euclidean plane , any measurable region can be divided into four equal (in measure) subsets (by ). Similarly, but more complicated, any measurable set in three-dimensional space can be divided into eight equal (in measure) subsets of three planes. However, this result is not generalized to five or higher dimensions, since the moment curve gives an example of sets that cannot be divided into 2 d subsets of d by hyperplanes. In particular, in a five-dimensional space, a set of five hyperplanes can split the moment curve into no more than 26 segments. It is not known whether it is always possible to divide the moment curve in four-dimensional space into 16 equal parts by five hyperplanes, but it is possible to divide 16 points on the four-dimensional moment curve into 16 orthants of a set of four hyperplanes [9] [10] .
The construction based on the curve of moments can also be used to prove the Gale lemma, according to which for any positive k and d one can place 2 k + d points on a d- dimensional sphere in such a way that any open hemisphere contains at least k points. This lemma, in turn, can be used to calculate the chromatic number of Kneser graphs , a problem that Laszlo Lovas solved in a different way [11] [12] .
The moment curve is also used to visualize graphs to show that all graphs with n vertices can be drawn with vertices on a three-dimensional integer lattice with side length O ( n ) without intersecting edges. The main idea is to choose a prime number p greater than n , and put the vertices i of the graph at a point with coordinates
- ( i , i 2 mod p , i 3 mod p ) [13] .
Then the plane can cross the curve only at three points. Since two intersecting edges must have four vertices on the same plane, this cannot happen. Such a construction uses the moment curve modulo a prime number, but in two-dimensional space, and not in three-dimensional space, which gives a linear boundary of the number of points for the . [fourteen]
Notes
- ↑ Matoušek, 2002 , p. 97, Definition 5.4.1.
- ↑ Matoušek, 2003 , p. 17, Definition 1.6.3.
- ↑ Edelsbrunner, 1987 , p. one hundred.
- ↑ 1 2 Matoušek, 2002 , p. 97, Lemma 5.4.2.
- ↑ Matoušek, 2003 , p. 17, Lemma 1.6.4.
- ↑ Gale, 1963 .
- ↑ Edelsbrunner, 1987 , p. 101.
- ↑ Amenta, Attali, Devillers, 2007 .
- ↑ Edelsbrunner, 1987 , p. 70–79.
- ↑ Matoušek, 2003 , p. 50-51.
- ↑ Matoušek, 2003 , p. 64–67, Section 3.5, Gale's Lemma and the Scraver Theorem.
- ↑ Bárány, 1978 , p. 325–326, The use of Gale's lemma for the coloring problem.
- ↑ Cohen, Eades, Lin, Ruskey, 1997 .
- ↑ Roth ( Roth 1951 ) attributes the task to Erdös .
Literature
- Nina Amenta, Dominique Attali, Olivier Devillers. Complexity of Delaunay triangulation for points on lower-dimensional polyhedra // Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. - New York: ACM, 2007 .-- S. 1106–1113. .
- Bárány I. A short proof of Kneser's conjecture // Journal of Combinatorial Theory . - 1978. - T. 25 , no. 3 . - DOI : 10.1016 / 0097-3165 (78) 90023-7 .
- Cohen RF, Eades P., Lin Tao, Ruskey F. Three-dimensional graph drawing // Algorithmica . - 1997. - T. 17 , no. 2 . - S. 199–208 . - DOI : 10.1007 / BF02522826 .
- Herbert Edelsbrunner. Algorithms in Combinatorial Geometry. - Berlin: Springer-Verlag, 1987. - T. 10. - (EATCS Monographs on Theoretical Computer Science). - ISBN 3-540-13722-X .
- David Gale. Neighborly and cyclic polytopes // Convexity, Seattle, 1961 / Victor Klee. - Providence, RI: American Mathematical Society, 1963. - T. 7. - S. 225–232. - (Symposia in Pure Mathematics).
- Jiří Matoušek. Lectures on Discrete Geometry. - Springer-Verlag, 2002. - T. 212. - ( Graduate Texts in Mathematics ). - ISBN 978-0-387-95373-1 .
- Jiří Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. - Springer, 2003. - (Universitext). - ISBN 978-3-540-00362-5 .
- Roth KF On a problem of Heilbronn // Journal of the London Mathematical Society . - 1951. - T. 26 , no. 3 . - S. 198–204 . - DOI : 10.1112 / jlms / s1-26.3.198 .