Title: An improved lower bound for general position subset selection

Authors: Ali Gholami Rudi

Addresses: Faculty of Electrical and Computer Engineering, Babol Noshirvani University of Technology, Babol, Iran

Abstract: 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 s is the size the optimal solution, the square root of s 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.

Keywords: general position subset selection; GPSS; collinearity testing; computational geometry.

DOI: 10.1504/IJCSM.2017.088974

International Journal of Computing Science and Mathematics, 2017 Vol.8 No.6, pp.562 - 569

Received: 04 May 2017
Accepted: 13 Jun 2017

Published online: 03 Jan 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article