Given many points, find if any of the three points is collinear

Question

What is the best search algorithm if any three points are collinear in the set of points, say n. Please also explain complexity if this is not trivial.

thank
Bala

Answer 1

If you can find the best O (N ^ 2) algorithm, you can post it!

This problem is 3-SUM Hard , and is there a sub-quadratic algorithm (i.e. better than O (N ^ 2)) since this is an open problem. It has been shown that many common computational geometry problems (including yours) are 3SUM complex, and this class of problems is growing. Like NP-Hardness, the 3SUM-Hardness concept has proven useful in proving the “hardness” of some problems.

To prove that your problem is 3SUM, refer to the excellent paper with the inscription 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 article.

So, the most famous algorithm at present is O (N ^ 2), and you already have it :-)

Answer 2

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

• Create a bounding rectangle around the set of points (make it large enough so that there are no points on the border)
• For each pair of points, calculate the line passing through them.
• For each row, compute two collision points with a bounding box.
• Two collision points define the source line, so if there are matching lines, they will also create the same two collision points.
• Use a hash set to determine if there are duplicate pairs of collision points.
• There are 3 collinear points if and only if there were duplicates.

Answer 3

Another simple (possibly even trivial) solution that does not use a hash table works in O (n ² log n) time and uses O (n) space:

Let S be the set of points, we describe an algorithm that finds out whether or not S contains three collinear points.

• For each point o in S do:
  • Line L along the x axis with o .
  • Replace each point in S below L , with its reflection. (For example, if L is the x axis, (a,-x) for x>0 after reflection it will become (a,x) . Let a new set of points S'
  • The angle of each point p in S' is the right angle of the segment po with the line L Compare the points S' at their angles.
  • Go through the sorted points in S' . If there are two consecutive points collinear with o , return the truth.
• If no collinear points are found in the loop, return false.

The loop starts n times, and each iteration performs nlog n steps. It is easy to prove that if there are three points on the line, they will be found, and we will not find anything.