Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 23, 2013, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Komei Fukuda
Keywords: simplex, Camion basis, depth-first-search tree
Given an arrangement of hyperplanes h1, h2,..., hm in the Euclidean (or projective) d-dimensional space with m >= d, consider a problem of finding a simplex region (i.e. a full dimensional cell which is a simplex). R.W. Shannon (1979) showed that under simple assumptions, namely (1) h1, h2,..., hm have no common intersection and (2) every d hyperplanes have a nonempty intersection, there is always a simplex region. Note that for the projective case, the assumption (2) is unnecessary.
The problem of finding either a simplex or a certificate of violation of an assumption cannot be NP-hard unless NP=coNP. Yet, the complexity of this problem is unknown in general.
Polynomial algorithms for special cases were found, interestingly, in a totally different setting. Given an d times m rational matrix A with rank(A) = d (i.e. row full rank). find a column basis B of A such that B-1 N is a nonnegative matrix after proper signing. Here A = [B; N] and a signing of a matrix is negating some rows and columns of the matrix. Such a basis is known as a Camion basis, as the existence was proven by Camion (1968). It turns out that the simplex regions and the Camion bases are essentially the same thing. Fonlupt-Raco (1984) gave a polynomial algorithm for the totally unimodular case, and F.-Musitelli (2006) proposed an algorithm which runs in polynomial time when the bases have bounded determinants.
In this talk, we will see how these problems are related, and look at some geometric ideas and observations which might be interesting for the future investigation.
Automatic MiSe System Software Version 1.4803M | admin login