8 citations · 19 across the 13 of their papers we have counts for
25 papers
Cookie cutters: Bisections with fixed shapes
Patrick Schnider, Pablo Soberón
In a mass partition problem, we are interested in finding equitable partitions of smooth measures in . In this manuscript, we study the problem of finding simultaneou…
A Topological Version of Schaefer's Dichotomy Theorem
Patrick Schnider, Simon Weber
Schaefer's dichotomy theorem [Schaefer, STOC'78] states that a boolean constraint satisfaction problem (CSP) is polynomial-time solvable if one of six given conditions holds for ev…
An FPT Algorithm for Splitting a Necklace Among Two Thieves
Michaela Borzechowski, Patrick Schnider, Simon Weber
It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the PPA-completeness…
Decomposition of Geometric Graphs into Star Forests
János Pach, Morteza Saghafian, Patrick Schnider
We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on vertices cannot be decomposed into fewer than star-forests, each consi…
On Connectivity in Random Graph Models with Limited Dependencies
Johannes Lengler, Anders Martinsson, Kalina Petrova +4
For any positive edge density , a random graph in the Erdős-Renyi model is connected with non-zero probability, since all edges are mutually independent. We consider r…
On the Complexity of Recognizing Nerves of Convex Sets
Patrick Schnider, Simon Weber
We study the problem of recognizing whether a given abstract simplicial complex is the -skeleton of the nerve of -dimensional convex sets in . We denote thi…
Combinatorial Depth Measures for Hyperplane Arrangements
Patrick Schnider, Pablo Soberón
Regression depth, introduced by Rousseeuw and Hubert in 1999, is a notion that measures how good of a regression hyperplane a given query hyperplane is with respect to a set of dat…
Well-Separation and Hyperplane Transversals in High Dimensions
Helena Bergold, Daniel Bertschinger, Nicolas Grelier +2
A family of point sets in dimensions is well-separated if the convex hulls of any two disjoint subfamilies can be separated by a hyperplane. Well-separation is a strong ass…
Edge Partitions of Complete Geometric Graphs (Part 2)
Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber +5
Recently, the second and third author showed that complete geometric graphs on vertices in general cannot be partitioned into plane spanning trees. Building up on this wor…
The complexity of sharing a pizza
Patrick Schnider
Assume you have a 2-dimensional pizza with ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then…
Topological Art in Simple Galleries
Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow +2
Let be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in . We say two points can see each…
Tukey Depth Histograms
Daniel Bertschinger, Jonas Passweg, Patrick Schnider
The Tukey depth of a flat with respect to a point set is a concept that appears in many areas of discrete and computational geometry. In particular, the study of centerpoints, cent…
Enclosing Depth and other Depth Measures
Patrick Schnider
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…
Weighted Epsilon-Nets
Daniel Bertschinger, Patrick Schnider
Motivated by recent work of Bukh and Nivasch on one-sided -approximants, we introduce the notion of \emph{weighted -nets}. It is a geometric notion of app…
Efficiently stabbing convex polygons and variants of the Hadwiger-Debrunner -theorem
Justin Dallant, Patrick Schnider
Hadwiger and Debrunner showed that for families of convex sets in with the property that among any of them some have a common point, the whole family can be…
Arrangements of Approaching Pseudo-Lines
Stefan Felsner, Alexander Pilz, Patrick Schnider
We consider arrangements of pseudo-lines in the Euclidean plane where each pseudo-line is represented by a bi-infinite connected -monotone curve , $x \in \m…
On the Average Complexity of the -Level
Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher +3
Let be an arrangement of lines in the Euclidean plane. The \emph{-level} of consists of all vertices of the arrangement which have exactly line…
Equipartitions with Wedges and Cones
Patrick Schnider
A famous result about mass partitions is the so called \emph{Ham-Sandwich theorem}. It states that any mass distributions in can be simultaneously bisected by a…
Bisecting three classes of lines
Alexander Pilz, Patrick Schnider
We consider the following problem: Let be an arrangement of lines in colored red, green, and blue. Does there exist a vertical plane such that…
Sharing a pizza: bisecting masses with two cuts
Luis Barba, Alexander Pilz, Patrick Schnider
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…
Ham-Sandwich cuts and center transversals in subspaces
Patrick Schnider
The Ham-Sandwich theorem is a well-known result in geometry. It states that any mass distributions in can be simultaneously bisected by a hyperplane. The result…
Extending the centerpoint theorem to multiple points
Alexander Pilz, Patrick Schnider
The centerpoint theorem is a well-known and widely used result in discrete geometry. It states that for any point set of points in , there is a point , not…
The Partition Spanning Forest Problem
Philipp Kindermann, Boris Klemz, Ignaz Rutter +2
Given a set of colored points in the plane, we ask if there exists a crossing-free straight-line drawing of a spanning forest, such that every tree in the forest contains exactly t…
Even flying cops should think ahead
Anders Martinsson, Florian Meier, Patrick Schnider +1
We study the entanglement game, which is a version of cops and robbers, on sparse graphs. While the minimum degree of a graph G is a lower bound for the number of cops needed to ca…