A Center Transversal Theorem for Hyperplanes Arrangements

演讲人: Stefan Langerman 布鲁塞尔自由大学
时间: 2012-08-13 14:00-2012-08-13 15:00
地点:FIT 1-222
课件下载:点击下载
内容:

Motivated by an open problem from graph drawing, we study several partitioning problems for line and hyperplane arrangements. We prove a ham-sandwich cut theorem: given two sets of n lines in R^2, there is a line L such that in both line sets, for both halfplanes delimited by L, there are sqrt{n} lines which pairwise intersect in that halfplane, and this bound is tight; a centerpoint theorem: for any set of n lines there is a point such that for any halfplane containing that point there are Omega(sqrt{n}) of the lines which pairwise intersect in that halfplane.
We generalize those results in higher dimension and obtain a center transversal theorem, a same-type lemma, and a positive fraction Erdos-Szekeres theorem for hyperplane arrangements. This is done by formulating a generalization of the center transversal theorem which applies to set functions that are much more general than measures. Back to Graph Drawing (and in the plane), we completely solve the open problem that motivated our search: there is no set of n labelled lines that are universal for all n-vertex labelled planar graphs.
This is joint work with Vida Dujmovic.

个人简介:

Stefan Langerman obtained his Ph.D. from Rutgers University in 2001. In 2002 he joined the Computer Science Department at the Université Libre de Bruxelles (ULB) in Belgium where he is currently Associate Professor and Research Director for the FNRS (Belgian Research Foundation). His main research interests are in Discrete and Computational Geometry, Algorithms and Data Structures.