16

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

Gabriel Ščerbák
  • 18,240
  • 8
  • 37
  • 52
Boolean
  • 14,266
  • 30
  • 88
  • 129
  • 2
    This question was discussed in the class and I know the O(N^2) algorithm. I found quite simple algorithm to do it in O(N^2). I want to know if there is an even simpler algorithm. – Boolean Apr 29 '10 at 02:01
  • yes there are 2d points. – Boolean Apr 29 '10 at 02:28
  • 1
    This and another question Algorist asked are both Google interview questions. – FogleBird Apr 29 '10 at 02:30
  • @Algorist: Not sure if you can be notified of my answer, hence the ping using a comment. Hope it proves useful. –  May 07 '10 at 05:00
  • 4
    @Algorist - can you share with us the simple O(N^2) algorithm? I haven't found anything simple... – Elazar Leibovich Jul 09 '10 at 07:15
  • @FogleBird This is also a (modified) question from the Introduction to Algorithms text, the computational geometry chapter. – Dennis Mar 03 '12 at 22:05

3 Answers3

17

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

  • @Moron - is there an algorithm with time `O(n^2)` which isn't using hash table as the one described by @Strilanc? – Elazar Leibovich Jul 08 '10 at 06:26
  • 1
    @Elazar: I believe it is possible, by considering the dual in which lines maps to points and vice versa (a,b) <-> y = ax+b . Now the problem corresponds to finding vertices in the dual with degree at least 6. Apparently this is possible in O(n^2) time and O(n^2) space. This book: http://books.google.com/books?id=PBRJ-ruwOQcC has a mention of it on page 94. –  Jul 08 '10 at 06:51
  • This answer is slightly out of date now; subquadratic algorithms for 3SUM were published after this answer was posted. Simple quadratic algorithms are probably most useful in practice though. – Daniel Lubarov Jan 27 '21 at 17:38
8

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.
Craig Gidney
  • 17,763
  • 5
  • 68
  • 136
  • Your condition is necessary, but is it sufficient? Put 4 points at (0,0), (0,1), (1,0), and (1,1) to define the bounding box. The pair [(0.5,0.6), (0.5,0.7)] creates a segment that intersects the box at (0.5,0), as does the pair [(0.4,0.1),(0.3,0.2)]. Yet no three of the 8 points are on any common line. – Eric Apr 29 '10 at 14:45
  • 1
    It's a sufficient condition because two points define a line. You've only considered one of the points in the collision point pair; the other one will differ, so the pair doesn't match. – Craig Gidney Apr 29 '10 at 15:09
  • 1
    Right you are. You might want to give more detail, in step 2, to clarify that the two collision points are put together to create a "collision point pair". Otherwise a reader may confuse the pair (of collision points) in step 3 with the pair (of original points) in step 2, as I did. – Eric May 01 '10 at 00:09
  • 1
    Oh I see, you interpreted 'pairs' as two equal collision points instead of two pairs of equal collisions points. – Craig Gidney May 01 '10 at 03:25
4

Another simple (maybe even trivial) solution which doesn't use a hash table, runs in O(n2log 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.

Elazar Leibovich
  • 32,750
  • 33
  • 122
  • 169
  • You only need to do the outer loop for half of the points: those with largest `y` coordinate values, correct? Also when you said "there are two consecutive points which are collinear", you actually meant "there are two consecutive points which are collinear together with point `o`", am I understanding you correctly? – Qiang Li Oct 16 '11 at 00:59
  • 1
    First observation is correct, although it does not change the complexity. Doing so for the other half of the points is equivalent due to symmetry. Note that you have to sort them first, which makes the algorithm a bit more complex.. The second point is also correct, fixing it, Thanks. – Elazar Leibovich Oct 16 '11 at 07:34