27 citations · 66 across the 11 of their papers we have counts for
Showing 2011 · cs.CGShow all
3 papers · 2 filters
cs.CG2011
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…
cs.CG2011★ 27 cited
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…
cs.CG2011★ 4 cited
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…