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.

Depth Measures for high-dimensional data

Depth measures are a way to generalize the concept of a median to higher dimensions. Several different depth measures have been introduced in the literature, all of which lead to interesting combinatorial and computational questions. I am particularly interested in the relationship between different measures and the depth structures that they induce on a data set in high dimensions.

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.

Enclosing Depth and other Depth MeasuresISAAC 2021

We study families of depth measures defined by natural sets of axioms. We show that any such depth measure is a constant factor approximation of Tukey depth. We further investigate the dimensions of depth regions, showing that the Cascade conjecture, introduced by Kalai for Tverberg depth, holds for all depth measures which satisfy our most restrictive set of axioms, which includes Tukey depth. Along the way, we introduce and study a new depth measure called enclosing depth, which we believe to be of independent interest, and show its relation to a constant-fraction Radon theorem on certain two-colored point sets.

Topological Art in Simple GalleriesSOSA 2022

Let P be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in P. We say two points a,b in P can see each other if the line segment between then is contained in P. We denote by V(P) the family of all minimum guard placements. The Hausdorff distance makes V(P) a metric space and thus a topological space. We show homotopy-universality, that is for every semi-algebraic set S there is a polygon P such that V(P) is homotopy equivalent to S. Furthermore, for various concrete topological spaces T, we describe instances I of the art gallery problem such that V(I) is homeomorphic to T.

Home / Research