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

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 h₁, h₂,..., 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₁, h₂,..., 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