Patrick Schnider

My Research

For a list of my publications, visit my profiles on Google Scholar and dblp.

Topological Methods

The well-known Ham-Sandwich Theorem states that any d masses in d-dimensional space can be simultaneously bisected by a single hyperplane. The proof of this result uses tools from algebraic topology, namely the famous Borsuk-Ulam Theorem. A natural question now is to ask, whether we can bisect even more masses, if we use more or different types of cuts. For many such questions, new topological tools, similar to the Borsuk-Ulam Theorem, are required.

Geometric Transversals

The study of Geometric Transversal has its origins in the following Theorem of Helly: given a family of convex sets in d-dimensional space, such that any d+1 of them have a point in common, then all the sets in the family have a point in common. The general goal of Geometric Transversals is to hit a family of sets with as few smaller sets as possible (in Helly's case with a single point). I am particularly interested in problems, where the ambient space is not the Euclidean space.

Combinatorics of Point Sets

Many problems on point sets (e.g. finding a Ham-Sandwich cut, size of the largest family of pairwise crossing segments,...) do not depend on the actual coordinates of the points, but only on their relative positions, the so-called Order Types. Among the many open problems related with point sets, one that caught my attention the most is the question how many crossing-free spanning trees can be packed into the complete geometric graph drawn on the given point set. This was my first research project, started with my Master's Thesis

Some selected papers

Here you find a selection of some of my recent papers.

Ham-Sandwich cuts and center transversals in subspacesSoCG 2019

Given a continuous assignment of mass distributions to certain subsets of d-dimensional Euclidean space, is there a subset on which we can bisect more masses than what is guaranteed by the Ham-Sandwich Theorem? We investigate two types of subsets. The first are linear subspaces, for which we show that there is always a subspace in which we can bisect as many masses as we could in the total space, proving a conjecture of Barba along the way. This result is also extended to center transversals. The second type of subsets are subsets that are defined by families of hyperplanes. Also in this case, we find a Ham-Sandwich-type result. We further use the underlying topological result to prove a conjecture by Langerman in a relaxed setting.

Extending the Centerpoint Theorem to Multiple PointsISAAC 2018

A centerpoint is a generalization of a median to higher dimensions. In other words, a centerpoint can be interpreted as a good representative for a point set. But what if we allow more than one representative? For example in one-dimensional data sets, often certain quantiles are chosen as representatives instead of the median. We present a possible extension of the concept of quantiles to higher dimensions. The idea is to find a set of (few) points such that every halfspace that contains one point of them contains a large fraction of the data points and every halfspace that contains more of them contains an even larger fraction of the data points.

Sharing a pizza: bisecting masses with two cutsCCCG 2017

Assume you have a pizza consisting of four ingredients (e.g., bread, tomatoes, cheese and olives) that you want to share with your friend. You want to do this fairly, meaning that you and your friend should get the same amount of each ingredient. How many times do you need to cut the pizza so that this is possible? We will show that two straight cuts always suffice. More formally, we will show the following extension of the well-known Ham-sandwich theorem: Given four mass distributions in the plane, they can be simultaneously bisected with two lines.

Home / Research