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

Abstract

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 the) problem is W[1]-hard.

9 pages, 8 figures