Efficient algorithms for the hitchcock transportation problem
Takeshi Tokuyama, Jun Nakano
SODA 1992
Let Γ be a collection of unbounded x-monotone Jordan arcs intersecting at most twice each other, which we call pseudoparabolas, since two axis parallel parabolas intersect at most twice. We investigate how to cut pseudoparabolas into the minimum number of curve segments so that each pair of segments intersect at most once. We give an Ω (n4/3) lower bound and O (n5/3) upper bound on the number of cuts. We give the same bounds for an arrangement of circles. Applying the upper bound, we give an O (n23/12) bound on the complexity of a level in an arrangement of pseudoparabolas, and an O (n11/6) bound on the complexity of a combinatorially concave chain of pseudoparabolas. We also give some upper bounds on the number of transitions of the minimum weight matroid base when the weight of each element changes as a quadratic function of a single parameter.
Takeshi Tokuyama, Jun Nakano
SODA 1992
Hisao Tamaki
SPAA 1994
Nader H. Bshouty, Sally A. Goldman, et al.
Journal of the ACM
Alok Aggarwal, Takeshi Tokuyama
Journal of Algorithms