research
∙
07/07/2023
A Topological Version of Schaefer's Dichotomy Theorem
Schaefer's dichotomy theorem [Schaefer, STOC'78] states that a boolean c...
share
research
∙
06/26/2023
An FPT Algorithm for Splitting a Necklace Among Two Thieves
It is well-known that the 2-Thief-Necklace-Splitting problem reduces to ...
research
∙
06/22/2023
Decomposition of Geometric Graphs into Star Forests
We solve a problem of Dujmović and Wood (2007) by showing that a complet...
research
∙
02/26/2023
On the Complexity of Recognizing Nerves of Convex Sets
We study the problem of recognizing whether a given abstract simplicial ...
research
∙
02/15/2023
Combinatorial Depth Measures for Hyperplane Arrangements
Regression depth, introduced by Rousseeuw and Hubert in 1999, is a notio...
research
∙
09/06/2022
Well-Separation and Hyperplane Transversals in High Dimensions
A family of k point sets in d dimensions is well-separated if the convex...
research
∙
12/15/2021
Edge Partitions of Complete Geometric Graphs (Part 2)
Recently, the second and third author showed that complete geometric gra...
research
∙
09/14/2021
The complexity of sharing a pizza
Assume you have a 2-dimensional pizza with 2n ingredients that you want ...
research
∙
08/09/2021
Topological Art in Simple Galleries
Let P be a simple polygon, then the art gallery problem is looking for a...
research
∙
03/15/2021
Tukey Depth Histograms
The Tukey depth of a flat with respect to a point set is a concept that ...
research
∙
03/15/2021
Enclosing Depth and other Depth Measures
We study families of depth measures defined by natural sets of axioms. W...
research
∙
02/20/2020
Weighted Epsilon-Nets
Motivated by recent work of Bukh and Nivasch on one-sided ε-approximants...
research
∙
02/17/2020
Efficiently stabbing convex polygons and variants of the Hadwiger-Debrunner (p, q)-theorem
Hadwiger and Debrunner showed that for families of convex sets in ℝ^d wi...
research
∙
01/23/2020
Arrangements of Approaching Pseudo-Lines
We consider arrangements of n pseudo-lines in the Euclidean plane where ...
research
∙
11/06/2019
On the Average Complexity of the k-Level
Let A be an arrangement of n lines in the Euclidean plane. The <i>k-leve...
research
∙
10/29/2019
Equipartitions with Wedges and Cones
A famous result about mass partitions is the so called Ham-Sandwich theo...
research
∙
09/10/2019
Bisecting three classes of lines
We consider the following problem: Let L be an arrangement of n lines in...
research
∙
04/04/2019
Sharing a pizza: bisecting masses with two cuts
Assume you have a pizza consisting of four ingredients (e.g., bread, tom...
research
∙
03/29/2019
Ham-Sandwich cuts and center transversals in subspaces
The Ham-Sandwich theorem is a well-known result in geometry. It states t...
research
∙
10/24/2018
Extending the centerpoint theorem to multiple points
The centerpoint theorem is a well-known and widely used result in discre...
research
∙
09/07/2018
The Partition Spanning Forest Problem
Given a set of colored points in the plane, we ask if there exists a cro...
research
∙
01/22/2018