 Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, February 26, 2019, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Patrick Schnider

Center transversals in subspaces

The center transversal theorem is a result which generalizes both the centerpoint theorem and the Ham-Sandwich theorem, two famous theorems from discrete geometry. The statement of the center transversal theorem is as follows: Given any k mass distributions in d-dimensional space, there exists a (k-1)-dimensional affine subspace g, called a (k-1)-center transversal, such that any halfspace containing g contains at least a (1/(d-k+2))-fraction of each mass. Setting k=d, we get the statement of the Ham-Sandwich theorem, while setting k=1 gives the centerpoint theorem. Assume now that you are given a continuous assignment of t mass distributions to every linear d-dimensional subspace of an n-dimensional space. Is there a subspace where you can find a center transversal for more than d masses? The answer is yes, there is always a subspace where you can find a (k-1)-center transversal for t=k+n-d masses. In this talk, which can be seen as a continuation of my last talk "Ham Sandwich Cuts in Subspaces", we will look at some concepts used in the proof of this result.

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

Information for students and suggested topics for student talks