KATOH Naoki, TAMAKI Hisao, TOKUYAMA Takeshi
IPSJ SIG Notes, 1998(41) 49-56, May 20, 1998
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Ο(κ^1/3η)upper bound on the number of k-set(and complexity of k-level of an arrangement), David Eppstein's lower bound on the transition of the minimum weight base of a parametric matroid, and also the 【○!-】(κη)bound for the complexity of at-most-k level(union of i-levels for i=1, 2, .., κ)of the arrangement. As applications, we improve Welzl's upper bound of the sum of complexities of multiple levels, and considered the number of different equal-sized-bucketing of a planar point set with parallel partition lines.