Geometric algorithms for a minimum cost assignment problem
Takeshi Tokuyama, Jun Nakano
SCG 1991
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
SCG 1991
Komei Fukuda, Akihisa Tamura, et al.
Geometriae Dedicata
Takeshi Fukuda, Yasuhiko Morimoto, et al.
Journal of Computer and System Sciences
Yuichi Asahiro, Kazuo Iwama, et al.
Journal of Algorithms