### Abstract

We give an optimal bound on the number of transitions of the minimum weight base of an integer valued parametric polymatroid. This generalizes and unifies Tamal Dey's O(k^{1/3}n) upper bound on the number of k-sets (and the complexity of the k-level of a straight-line arrangement), David Eppstein's lower bound on the number of transitions of the minimum weight base of a parametric matroid, and also the Θ (kn) bound on the complexity of the at-most-k level (the union of i-levels for i = 1, 2, ..., k) of a straight-line arrangement. As applications, we improve Welzl's upper bound on the sum of the complexities of multiple levels, and apply this bound to the number of different equal-sized-bucketings of a planar point set with parallel partition lines. We also consider an application to a special parametric transportation problem.

Original language | English |
---|---|

Pages | 517-526 |

Number of pages | 10 |

Publication status | Published - 1 Jan 1999 |

Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: 17 Jan 1999 → 19 Jan 1999 |

### Conference

Conference | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | Baltimore, MD, USA |

Period | 17/01/99 → 19/01/99 |

## Fingerprint Dive into the research topics of 'Parametric polymatroid optimization and its geometric applications'. Together they form a unique fingerprint.

## Cite this

*Parametric polymatroid optimization and its geometric applications*. 517-526. Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, .