27 citations · 66 across the 11 of their papers we have counts for
7 papers · 1 filter
A Lower Bound for Shallow Partitions
Wolfgang Mulzer, Daniel Werner
Let P be a planar n-point set. A k-partition of P is a subdivision of P into n/k parts of roughly equal size and a sequence of triangles such that each part is contained in a trian…
Erdős-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3 dimensions - and what now?
Christian Knauer, Daniel Werner
We consider the computational versions of the Erd\H os-Szekeres theorem and related problems in 3 dimensions. We show that, in constrast to the planar case, no polynomial time algo…
Approximating Tverberg Points in Linear Time for Any Fixed Dimension
Wolfgang Mulzer, Daniel Werner
Let P be a d-dimensional n-point set. A Tverberg-partition of P is a partition of P into r sets P_1, ..., P_r such that the convex hulls conv(P_1), ..., conv(P_r) have non-empty in…
Hardness of discrepancy computation and epsilon-net verification in high dimension
Panos Giannopoulos, Christian Knauer, Magnus Wahlström +1
Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. There are two notions of discrepancy, namely continuous discrepancy and combina…
Polynomial Bounds on the Slicing Number
Daniel Werner, Matthias Lenz
NOTE: Unfortunately, most of the results mentioned here were already known under the name of "d-separated interval piercing". The result that T_d(m) exists was first proved by Gyaŕ…
Fixed-parameter tractability and lower bounds for stabbing problems
Panos Giannopoulos, Christian Knauer, Gunter Rote +1
We study the following general stabbing problem from a parameterized complexity point of view: Given a set of translates of an object in $\Rd$, find a set of l…