Improved bounds for planar k-sets and related problems

We prove an O(n(k + 1)(1/3)) upper bound for planar k-sets. This is the first considerable improvement on this bound after its early solution approximately 27 years ago. Our proof technique also applies to improve the current bound; on the combinatorial complexities of k-levels in the arrangement of line segments, k convex polygons in the union of n lines, parametric minimum spanning trees, and parametric matroids in general.