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

2013/03/31 by Giannopoulos, Panos, Knauer, Christian
#Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1304.0247

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.

Related

• Computing Largest Subsets of Points Whose Convex Hulls have Bounded Area and Diameter
• Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
• A Polynomial-Time Algorithm for Computing the Exact Convex Hull in High-Dimensional Spaces
• Computing Convex Partitions for Point Sets in the Plane: The CG:SHOP Challenge 2020
• Finding the vertices of the convex hull, even unordered, takes Omega(n log n) time -- a proof by reduction from epsilon-closeness