algorithm - Given a set of points, find if any of the three points are collinear

Question

What is the best algorithm to find if any three points are collinear in a set of points say n. Please also explain the complexity if it is not trivial.

Thanks
Bala

Answer 1

If you can come up with a better than O(N^2) algorithm, you can publish it!

This problem is 3-SUM Hard, and whether there is a sub-quadratic algorithm (i.e. better than O(N^2)) for it is an open problem. Many common computational geometry problems (including yours) have been shown to be 3SUM hard and this class of problems is growing. Like NP-Hardness, the concept of 3SUM-Hardness has proven useful in proving 'toughness' of some problems.

For a proof that your problem is 3SUM hard, refer to the excellent surver paper here: http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf

Your problem appears on page 3 (conveniently called 3-POINTS-ON-LINE) in the above mentioned paper.

So, the currently best known algorithm is O(N^2) and you already have it :-)