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

What is the best algori开发者_开发知识库thm 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

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 :-)

A simple O(d*N^2) time and space algorithm, where d is the dimensionality and N is the number of points (probably not optimal):

• Create a bounding box around the set of points (make it big enough so there are no points on the boundary)
• For each pair of points, compute the line passing through them.
• For each line, compute its two collision points with the bounding box.
• The two collision points define the original line, so if there any matching lines they will also produce the same two collision points.
• Use a hash set to determine if there are any duplicate collision point pairs.
• There are 3 collinear points if and only if there were duplicates.

Another simple (maybe even trivial) solution which doesn't use a hash table, runs in O(n²log n) time, and uses O(n) space:

Let S be a set of points, we will describe an algorithm which finds out whether or not S contains some three collinear points.

1. For each point o in S do:
   1. Pass a line L parallel to the x-axis through o.
   2. Replace every point in S below L, with its reflection. (For example if L is the x axis, (a,-x) for x>0 will become (a,x) after the reflection). Let the new set of points be S'
   3. The angle of each point p in S', is the right angle of the segment po with the line L. Let us sort the points S' by their angles.
   4. Walk through the sorted points in S'. If there are two consecutive points which are collinear with o - return true.
2. If no collinear points were found in the loop - return false.

The loop runs n times, and each iteration performs nlog n steps. It is not hard to prove that if there're three points on a line they'll be found, and we'll find nothing otherwise.