Abstract.
We relate the sequence of minimum bases of a matroid with linearly varying weights to three problems from combinatorial geometry: k -sets, lower envelopes of line segments, and convex polygons in line arrangements. Using these relations we show new lower bounds on the number of base changes in such sequences: Ω(nr 1/3 ) for a general n -element matroid with rank r , and Ω(mα(n)) for the special case of parametric graph minimum spanning trees. The only previous lower bound was Ω(n log r) for uniform matroids; upper bounds of O(mn 1/2 ) for arbitrary matroids and O(mn 1/2 / log * n) for uniform matroids were also known.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received November 12, 1996, and in revised form February 19, 1997.
Rights and permissions
About this article
Cite this article
Eppstein, D. Geometric Lower Bounds for Parametric Matroid Optimization . Discrete Comput Geom 20, 463–476 (1998). https://doi.org/10.1007/PL00009396
Issue Date:
DOI: https://doi.org/10.1007/PL00009396