Combinatorics on Arrangements and Parametric Matroids: A Bridge between Computational Geometry and Combinatorial Optimization

Takeshi TOKUYAMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E83-D    No.3    pp.362-371
Publication Date: 2000/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Algorithms for Matroids and Related Discrete Systems
parametric optimization,  computational geometry,  combinatorics,  matroids,  

Full Text: PDF>>
Buy this Article

Given a combinatorial problem on a set of weighted elements, if we change the weight using a parameter, we obtain a parametric version of the problem, which is often used as a tool for solving mathematical programming problems. One interesting question is how to describe and analyze the trajectory of the solution. If we consider the trajectory of each weight function as a curve in a plane, we have a set of curves from the problem instance. The curves induces a cell complex called an arrangement, which is a popular research target in computational geometry. Especially, for the parametric version of the problem of computing the minimum weight base of a matroid or polymatroid, the trajectory of the solution becomes a subcomplex in an arrangement. We introduce the interaction between the two research areas, combinatorial optimization and computational geometry, through this bridge.