Question

This is a type of question where you need to imagine & think.
if you were given a number of points on the cartesian plain, how would you draw a straight line so that it passes through most of the points?

Answer 1

1, no problem, 2 no problem, 3 no problem, so start with 4...

Answer 2

i am sorry can you explain it again

Answer 3

Just thinking out loud...

Obviously the cases of 1 point, 2 points and 3 points are not a problem (trivial if you like).

So the first case of interest is 4 points where you can manage a line through 3 if you get lucky and only 2 if not (ie most of the time).

Answer 4

what would you do if u were given a set of 100 points in the form of (x,y)??

Answer 5

I'd have to test them with a program....

Answer 6

Have to think about the complexity of that, running time, etc...

See if there is some efficient algorithm.

Answer 7

i want that algorithm

Answer 8

It is called "Curve fitting" (finding the general equation for a set of discrete data value). Mathematica does it very well (with the Fit[] function)

Answer 9

Hmm, the requirement "pass through" is not quite the same as "best fit"...

Answer 10

You are absolutly right. But I presume what the OP is searching is fitting, as a 100+ points problem is very uncommon.

Answer 11

this is not a question to be solved in the exam. it jst checks ur imagination

Answer 12

sir are we allowed to go in further dimensions ? we can fold the 2nd dimension into a 3rd dimension....like they do it in string theory ??

Answer 13

For passthough, one naive algorithm would be :

curr_number_point_passtrough = 0
max_number_point_passtrough = 0
bestmatch = NULL
forall (a,b) in (point,point)
{
e = find_equation(a,b)
forall c in point
{
if(e(a) == true)
curr_number_point_passtrough++
}
if(curr_number_point_passtrough > max_number_point_passtrough)
{
max_number_point_passtrough = curr_number_point_passtrough
bestmatch = e
}
}

Answer 14

Correction : it's " if(e(c) == true)"

Answer 15

Thinking about this a bit, it's something of a problem, since you are likely going to have some outliers if the point selection is just random and you would first want to eliminate these.

This would be much less of a problem for experimental data where, depending on the experiment, more points are likely to lie on or near a line.

Answer 16

However, if point are distribued randomly, it is very likely that any line that cross at least two point also cross a total number of point close to the maximum number of point crossed.

Answer 17

I think OP has to specify the problem a bit more.

Even with relatively few random points, the likelihood is you cannot pass through a majority.

Answer 18

My attempt with 100 pair of coordinates, creating linking line between 2 points : http://i.imgur.com/1MPBu.png

No more than 4 point in a lign with a normal distribution of 100 pts.

Answer 19

Yes, that just about says it all, really:-)