## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, May 23, 2013, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Komei Fukuda

## Searching for a simplex region

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.

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login