Sets in Almost General Position

Abstract

Erdå's asked the following question: Given n points in the plane in almost general position (no four collinear), how large a set can we guarantee to find that is in general position (no three collinear)? Füredi constructed a set of n points in almost general position with no more than o(n) points in general position. Cardinal, Tóth and Wood extended this result to R3, finding sets of n points with no five in a plane whose subsets with no four points in a plane have size o(n), and asked the question for higher dimensions: For given n, is it still true that the largest subset in general position we can guarantee to find has size o(n)? We answer their question for all d and derive improved bounds for certain dimensions.