Finding Points in General Position

作     者：Vincent Froese Iyad Kanj André Nichterlein Rolf Niedermeier 

作者机构：Institut für Softwaretechnik und Theoretische Informatik TU Berlin Germany School of Computing DePaul University Chicago USA 

出 版 物：《International Journal of Computational Geometry & Applications》 

年 卷 期：2018年第27卷第4期

页      面：277-296页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Computational complexity parameterized complexity kernelization hardness of approximation point line cover 

摘      要：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.