0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mehrdad Dec 15 '15 at 17:38
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ok.but how to determine number of collinear points between the n points? $\endgroup$ – Mehrdad Dec 15 '15 at 12:23
  • $\begingroup$ I have generalized it. It should be given .we cant find it like that. Either the figure should be given or the points collinear from n .points $\endgroup$ – Archis Welankar Dec 15 '15 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.