Parametric polymatroid optimization and its geometric applications

Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama

Research output: Contribution to conferencePaper

4 Citations (Scopus)

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(k1/3n) 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 languageEnglish
Pages517-526
Number of pages10
Publication statusPublished - 1 Jan 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: 17 Jan 199919 Jan 1999

Conference

ConferenceProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period17/01/9919/01/99

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

  • Cite this

    Katoh, N., Tamaki, H., & Tokuyama, T. (1999). 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, .