On the General Position Subset Selection Problem

DOI10.1137/120897493zbMATH Open1348.52012arXiv1208.5289OpenAlexW2033635232MaRDI QIDQ5408587FDOQ5408587

Authors: Michael S. Payne, David R. Wood 

Publication date: 10 April 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $f(n,ell)$ be the maximum integer such that every set of $n$ points in the plane with at most $ell$ collinear contains a subset of $f(n,ell)$ points with no three collinear. First we prove that if $ellleqO(sqrtn)$ then $f(n,ell)geqOmega(sqrtfracnlnell)$. Second we prove that if $ellleqO(n^{(1-epsilon)/2})$ then $f(n,ell)geqOmega(sqrtnlo{g}_{e}lln)$, which implies all previously known lower bounds on $f(n,ell)$ and improves them when $ell$ is not fixed. A more general problem is to consider subsets with at most $k$ collinear points in a point set with at most $ell$ collinear. We also prove analogous results in this setting.

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

Recommendations

• An improved lower bound for general position subset selection
• A random-size subset approach to the selection problem
• A Generalized Problem of Optimal Selection and Assignment
• Deterministic and iterative solutions to subset selection problems
• Approximation schemes for a class of subset selection problems
• LATIN 2004: Theoretical Informatics
• On a variant of the problem of choosing a vector subset
• scientific article; zbMATH DE number 4147350
• scientific article; zbMATH DE number 176397

zbMATH Keywords

discrete geometrygeneral positionErdős problems

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Cited In (31)

• Characterization of classes of graphs with large general position number
• On subgraphs of bounded degeneracy in hypergraphs
• On the General Position Number of Complementary Prisms
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• On the number of points in general position in the plane
• The general position avoidance game and hardness of general position games
• General position sets in two families of Cartesian product graphs
• Finding points in general position
• The general position achievement game played on graphs
• Many collinear \(k\)-tuples with no \(k+1\) collinear points
• On higher-dimensional point sets in general position
• A general position problem in graph theory
• On general position sets in Cartesian products
• The general position problem on Kneser graphs and on some graph operations
• Sets in almost general position
• Kernelization of the subset general position problem in geometry
• General position subsets and independent hyperplanes in \(d\)-space
• Improved bound for the Gerver-Ramsey collinearity problem
• The general position number of Cartesian products involving a factor with small diameter
• Characterization of general position sets and its applications to cographs and bipartite graphs
• Ramsey-type theorems for lines in 3-space
• On independent position sets in graphs
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• Title not available (Why is that?)
• Convex polygons in Cartesian products
• The extensible no-three-in-line problem
• An improved lower bound for general position subset selection
• On the general position number of two classes of graphs
• On the general position number of Mycielskian graphs
• Additive combinatorics and graph theory
• The edge general position problem

This page was built for publication: On the General Position Subset Selection Problem

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