1 General Position

An set of 2D points is said to be in general position if any 3 points are not collinear. Given a set of points $P$ in the plane, find the largest subset $S\subset P$ in general position.

1.1 Related Problems/Works

• A recent paper [1] studied the “typical size” of the largest point set in general position in which each points is taken from ${\mathbb{F}}_q^3$ iid with probability $p$. “Typical size” means we want upper and lower bounds with high probability. Piror to this work, [2] gave an upperbound for the case of ${\mathbb{F}}_q^2$. A set of points $S\subset {\mathbb{F}}_q^d$ is in general position if there are no $d+1$ points in $S$ contained in a $(d-1)$-dimensional affine subspace. [1] also mentioned some non-random bounds. The max size of a point set in general position in ${\mathbb{F}}_q^d$ is at least $q$ and at most $(1+o(1))q$.
• [3] studied the problem of finding the largest subset of points in general position in a point set $P\subset {\mathbb{Q}}^2$. They showed that this problem is NP-hard, APX-hard and no $2^{o(n)}{n}^{O(1)}$-time alg under ETH.
• This blog post discusses constructions of general-position point sets $\subset {\mathbb{Z}}^2$ with some extremal structures.
• [4] improved the upperbound of the max number $a(d,k,n)$ of points selected from $[n{]}^d$ such that no $k+2$ members lie on a $k$-flat.

2 Integer Program and Duality

Let $P$ be a set of $n$ points in the plane. We can define $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ lines and write a point-line incidence matrix $A_{\left(\genfrac{}{}{0ex}{}{n}{2}\right)\times n}$ which indicates if point $p$ is on the line defined by $\{p_1,p_2\}$. Now we can write an IP for finding the largest subset of $P$ in general position.

$$\begin{array}{c}\begin{array}{rlrlrl}\max & & \sum _p& x_p& & \\ s.t.& & \sum _p& A_{i,p}{x}_p\le 2& & \forall i\in \left[\left(\genfrac{}{}{0ex}{}{n}{2}\right)\right]\\ & & & x_p\in \left\{0,1\right\}& & \end{array}\end{array}$$

Consider its LP dual,

$$\begin{array}{c}\begin{array}{rlrlrl}\min & & \sum _i& 2y_i& & \\ s.t.& & \sum _i& A_{i,p}{y}_i\ge 1& & \forall p\in P\\ & & & y_i\in \left\{0,1\right\}& & \end{array}\end{array}$$

One can see that the dual is finding the smallest number of lines to cover points in $P$. Denote by $\sigma$ the max number of general position points in $P$ and let $\alpha$ be the minimum line covering number. (Borrow these symbols from matroid strength and density.) There are some results in [3].

Now I am interested in the gaps of above IPs. It seems that in terms of approximation algorithms one can only get a $\sqrt{\sigma }$-approx P-time alg? (see master thesis of Cheng Cao and chatper 9 of David Eppstein’s book)

3 Open Problems

1. No-three-in-line problem

References