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

1.3k Views Asked by At

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?

1

There are 1 best solutions below

2
On

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.