# Minimum number of straight lines needed to cover $n$ points

Suppose we are given a set of $n$ points in the euclidean plane , they are distributed arbitarily (not in general position). what is the minimum number of lines in the plane needed to cover them all?

• your answer is the maximum, look the paper by Grantson "covering a set of points with a minimum number of lines" eurocg.org/06/delaunay.tem.uoc.gr/~mkaravel/ewcg06/papers/35.pdf – Mehrdad Dec 15 '15 at 17:38

The minimum number of lines is ${n\choose 2}-{k\choose 2}$ where n is the number of points while $k$ is number of points which are collinear if any.