0

The problem states that we receive an array of tuples, where each tuple represents a point, and we need to return the maximum number of colinear points.

I have already found a O(N^2) solution by comparing each point with every other one possible based on the same slope stored in a hash table.

I believe to have found a O(N) solution by considering each point as a vector.

If I compute the norm of each vector, and obtained the corresponding normalised vector, then if two normalised vectors are the same, it means that their correspondings heads point to colinear points. Is this correct?

If so I could build a hash table, traverse evey point once, storing the normalised vectors and whenever I found a repeated one it means I have another co-linear point to the point in question.

Thanks!

Marco

Marco Scilipoti
  • 3
  • 1
  • Since floating point math has limited precision, how do you define "same"? – stark Jul 26 '21 at 16:40
  • Depends. In your solution, two vectors are the same, if they form a line together with the origin of the coordinate system. Also normalization normally doesn't change the orientation of the vector, while for your problem rotations of `pi` should also be considered as equal. If both of these points apply, your solution is fine –  Jul 26 '21 at 16:46
  • 1
    Does this answer your question? [Maximum Collinear points in a plane](https://stackoverflow.com/questions/4386695/maximum-collinear-points-in-a-plane) –  Jul 26 '21 at 16:53
  • if the lines formed does not pass origin, then the normalized approach does not work. – Da Song Jul 26 '21 at 17:06
  • No, you can't work with the points in isolation, what you need to consider are the directions of *pairs of points*. –  Jul 27 '21 at 07:08
  • see [Given n points on a 2D plane, find the maximum number of points that lie on the same straight line](https://stackoverflow.com/a/20888844/2521214) ... what you describing is in bullet #3 ... however its not `O(n)` !!! but still fast ... also why [Hash] tag ? – Spektre Jul 30 '21 at 07:50

1 Answers1

3

This is not correct. If points are collinear on a line that does not pass through the origin, then the norms of the vectors pointing from the origin to the points can be all over the place.

btilly
  • 43,296
  • 3
  • 59
  • 88