2017/02/28 by Ali Gholami Rudi, Rudi, Ali Gholami
Computer Science · #05C69 #65D18 #Computational Geometry (cs.CG) #Constraint Satisfaction and Optimization #Data Management and Algorithms #FOS: Computer and information sciences #G.2.1 #G.2.2 #I.3.5 #Metaheuristic Optimization Algorithms Research #acm:05C69 #acm:65D18 #cs.CG #msc:05C69 #msc:65D18
paper · pdf · doi:10.48550/arxiv.1702.08654
Minor improvements in the presentation
openalex publication_date 2017/02/28 · arxiv created 2018/03/06 · arxiv updated 2018/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the General Position Subset Selection (GPSS) problem, the goal is to find the largest possible subset of a set of points such that no three of its members are collinear. If sGPSS is the size of the optimal solution, √sGPSS is the current best guarantee for the size of the solution obtained using a polynomial time algorithm. In this paper we present an algorithm for GPSS to improve this bound based on the number of collinear pairs of points. We experimentally evaluate this and few other GPSS algorithms; the result of these experiments suggests further opportunities for obtaining tighter lower bounds for GPSS.