Erd\H{o}s-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3   dimensions - and what now?
  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 algorithm exists for determining the largest (empty) convex subset (unless P=NP) among a set of points, by proving that the corresponding decision problem is NP-hard. This answers a question by Dobkin, Edelsbrunner and Overmars from 1990.   As a corollary, we derive a similar result for the closely related problem of testing weak epsilon-nets in R^3. Answering a question by Chazelle et al. from 1995, our reduction shows that the problem is co-NP-hard.   This is work in progress - we are still trying to find a smart approximation algorithm for the problems. 
Christian Knauer and Daniel Werner
cs.CG cs.CC