Finding Points in General Position

2017/12/01 by Vincent Froese, Iyad Kanj, André Nichterlein +1 · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Optimization and Search Problems #Cardinality (data modeling) #Position (finance) #General position #Selection (genetic algorithm) #Combinatorics #Set (abstract data type) #Mathematics #Plane (geometry) #Exponential function #Upper and lower bounds #Discrete mathematics #Computer science #Geometry #Mathematical analysis #Artificial intelligence

paper · doi:10.1142/s021819591750008x

openalex publication_date 2017/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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.

Citations

• On a Problem of Heilbronn
• Which Problems Have Strongly Exponential Complexity?
• On the General Position Subset Selection Problem
• The No-Three-In-Line Problem
• Some advances in the no-three-in-line problem
• Advice classes of parameterized tractability
• Constructing Arrangements of Lines and Hyperplanes with Applications

Cited by

• No-three-in-line problem [wikipedia]

Related

• Finding Points in General Position
• An Improved Lower Bound for General Position Subset Selection
• General Position Subset Selection in Line Arrangements
• On the General Position Subset Selection Problem
• Subset Selection Problems in Planar Point Sets