Finding a largest empty convex subset in space is W[1]-hard

Panos Giannopoulos, Christian Knauer

We consider the following problem: Given a point set in space find a largest subset that is in convex position and whose convex hull is empty. We show that the (decision version of…