Geometric lower bounds for parametric matroid optimization.
D. Eppstein.
Tech. Rep. 95-11, ICS, UCI, 1995.
27th ACM Symp. Theory of Computing, Las Vegas, 1995, pp. 662–671,
doi:10.1145/225058.225284.
Disc. Comp. Geom. 20: 463–476, 1998,
doi:10.1007/PL00009396.
Considers graphs in which edge weights are linear functions of time. Shows nonlinear lower bounds on the number of different minimum spanning trees appearing over time by translation from geometric problem of lower envelopes of line segments. A matroid generalization has a better lower bound coming from many faces in line arrangements, and the uniform matroid problem is equivalent to the geometric k-set problem.
I improved the \(\Omega(m\alpha(n))\) lower bound on minimum spanning trees from this paper to \(\Omega(m\log n)\) in my later paper "A stronger lower bound on parametric minimum spanning trees".