2013/09/04 by Imre Bárány, Barany, Imre, Jiřı́ Matoušek +3
Computer Science · Mathematics · #05D10 #52A10 #52C99 #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.1309.1147
openalex publication_date 2013/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
By a curve in Rd we mean a continuous map gamma:I -> Rd, where I is a closed interval. We call a curve gamma in Rd at most k crossing if it intersects every hyperplane at most k times (counted with multiplicity). The at most d crossing curves in Rd are often called convex curves and they form an important class; a primary example is the moment curve (t,t2,...,td):t∈[0,1]. They are also closely related to Chebyshev systems, which is a notion of considerable importance, e.g., in approximation theory. We prove that for every d there is M=M(d) such that every at most d+1 crossing curve in Rd can be subdivided into at most M convex curves. As a consequence, based on the work of Elias, Roldan, Safernova, and the second author, we obtain an essentially tight lower bound for a geometric Ramsey-type problem in Rd concerning order-type homogeneous sequences of points, investigated in several previous papers.