tom's blog

By tom, history, 5 years ago, In English


Having n points in the plane with the property that any 3 of them are collinear, how can I add point to it and maintain this property?

  • Vote: I like it
  • +2
  • Vote: I do not like it

5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If "any 3 of them are collinear" then they all belong to the same line. Every time you add a point to the set, check if it belongs to the same line. The general equation of the straight line is ax + by = c. These 3 coefficients are determined by the initial two points in the set. Then a point suffices the collinearity property if the equation still holds when you plug in its coordinates. O(1) insertion time.

If, on the other hand, neither of them belong to the same line; you can compute all the lines that pass through that new point and then check that no two of them are coincident. This would have a complexity of O(n) or O(n·logn) per insertion if you use hash or map respectively. This is probably much slower than what you originally intended but I can't think of any other solution (maybe some approximation algorithm?). Anyway, it's a good starting point for those who are unfamiliar with the topic.