Erdős-Szekeres and Testing Weak ε-Nets are NP-hard in 3 dimensions- and what now?

The Erdős-Szekeres theorem states that, for every k, there is a number nk such that every set of nk points in general position in the plane contains a subset of k points in convex position. If we ask the same question for subsets whose convex hull does not contain any other point from the set, this is not true: as shown by Horton, there are sets of arbitrary size that do not contain an empty 7-gon. These questions have also been studied extensively from a computational point of view, and polynomial time algorithms for finding the largest (empty) convex set have been given for the planar case. In higher dimension, it was not known how to compute such a set efficiently. In this paper, we show that already in dimension 3 no polynomial time algorithm exists for determining the largest (empty) convex set (unless P=NP), 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 ε-nets in R3. Answering a question by Chazelle et al. from 1995, our reduction shows that the problem is co-NP-hard.