Given a set of $n$ point in a plane, find the maximal number of colinear points (the points residing on the same straight line).The crudest algorithm is to compute the slope and intercept of each pair of point, assuming infinite precision, find maximal number of appearance of the same pair of parameters. Is there an algorithm more efficient (1) in the worst case, (2) on average? What is the optimal one (1) in the worst case which I suspect the crude method with complexity $n\choose 2$ is the optimal, (2) on average; and how to prove it?
Optimal Algorithm for Finding Maximal Number of Colinear Points
algorithms;algorithm analysis;computational geometry