An improved lower bound for general position subset selection

DOI10.1504/IJCSM.2017.088974zbMATH Open1453.65047arXiv1702.08654MaRDI QIDQ2224238

Author name not available (Why is that?)

Publication date: 3 February 2021

Published in: (Search for Journal in Brave)

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_{mathrmGPSS}$ is the size of the optimal solution, $sqrt{s}_{mathrmGPSS}$ 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.

Full work available at URL: https://arxiv.org/abs/1702.08654

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: An improved lower bound for general position subset selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2224238)