How to use incidence bounds to cover points with lines
Ingo van Duijn
Aarhus University

In the Line Cover problem a set of $n$ points (in any dimension) is given and the task is to cover the points using at most $k$ lines. We present an algorithm that solves the problem in $O^*((ck/\log k)^k)$ for a universal constant $c$, whereas the previous fastest known algorithm solves the problem in $O^*((k/1.35)^k)$. The main idea of our algorithm is to try to cover (i.e. branch on choosing) lines covering many points first. By the incidence bound in the Szemer├ędi-Trotter theorem, we can bound the number of rich lines, giving a low branching in the initial phase of the algorithm. When the incidence bounds are not tight enough to guarantee good branching behaviour, we show that we have few enough points to efficiently switch to a base case algorithm running in $O^*(2^n)$.