Finding Points in General Position
Vincent Froese, Iyad A. Kanj, André Nichterlein, Rolf Niedermeier · International Journal of Computational Geometry & Applications · 2017
We study the General Position Subset Selection problem: Given a set of points in the plane, find a maximum-cardinality subset of points in general position. We prove that General Position Subset Selection is NP-hard, APX-hard, and present several fixed-parameter tractability results for the problem as well as a subexponential running time lower bound based on the Exponential Time Hypothesis.