On the General Position Subset Selection Problem

DOI10.1137/120897493MaRDI QIDQ5408587zbMATH OpenOpenAlexFDO

Authors Michael S. Payne, David R. Wood

Publication date 10 April 2014

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

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

zbMATH Keywords

discrete geometryErdős problemsgeneral position

Mathematics Subject Classification ID

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

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.

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

Cited in

(38)

• Additive combinatorics and graph theory
• On general position sets in Cartesian products
• The general position problem on Kneser graphs and on some graph operations
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• On the general position number of two classes of graphs
• The edge general position problem
• The general position achievement game played on graphs
• An improved lower bound for general position subset selection
• 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
• General position subsets and independent hyperplanes in d-space
• Ramsey-type theorems for lines in 3-space
• On subgraphs of bounded degeneracy in hypergraphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Many collinear k-tuples with no k+1 collinear points
• scientific article; zbMATH DE number 2068103 (Why is no real title available?)
• Finding points in general position
• On the number of points in general position in the plane
• A general position problem in graph theory
• Characterization of classes of graphs with large general position number
• On the General Position Number of Complementary Prisms
• On independent position sets in graphs
• Convex polygons in Cartesian products
• Kernelization of the subset general position problem in geometry
• Sets in almost general position
• scientific article; zbMATH DE number 970816 (Why is no real title available?)
• General position sets in two families of Cartesian product graphs
• The extensible no-three-in-line problem
• Improved bound for the Gerver-Ramsey collinearity problem
• The general position avoidance game and hardness of general position games
• On the general position number of Mycielskian graphs
• On higher-dimensional point sets in general position
• A note on the edge general position number of cactus graphs
• General position subset selection in line arrangements
• The edge general position number of some graphs
• On the vertex position number of graphs
• The iteration time and the general position number in graph convexities
• The k-general d-position problem for graphs

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)