Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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**: OAT S15/S16/S17

**Speaker**: Komei Fukuda

Keywords: simplex, Camion basis, depth-first-search tree

Given an arrangement of hyperplanes h_{1}, h_{2},..., h_{m} 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) h_{1}, h_{2},..., h_{m} 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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login