CODEWITHSUNDEEP
mathhashmapgeometry
Donald
Donald

Reputation: 1340

Maximum number of points that lie on the same straight straight line in a 2D plane

I am trying to solve a programming interview question that requires one to find the maximum number of points that lie on the same straight straight line in a 2D plane. I have looked up the solutions on the web. All of them discuss a O(N^2) solution using hashing such as the one at this link: Here

I understand the part where common gradient is used to check for co-linear points since that is a common mathematical technique. However, the solution points out that one must beware of vertical lines and overlapping points. I am not sure how these points can cause problems? Can't I just store the gradient of vertical lines as infinity (a large number)?

Upvotes: 0

Views: 215

Answers (1)

John Alexiou
John Alexiou

Reputation: 29244

Hint:

Three distinct points are collinear if 

x_1*(y_2-y_3)+x_2*(y_3-y_1)+x_3*(y_1-y_2) = 0

No need to check for slopes or anything else. You need need to eliminate duplicate points from the set before the search begins though.

So pick a pair of points, and find all other points that are collinear and store them in a list of lines. For the remainder points do the same and then compare which lines have the most points.

The first time around you have n-2 tests. The second time around you have n-4 tests because there is no point on revisiting the first two points. Next time n-6 etc, for a total of n/2 tests. At worst case this results in (n/2)*(n/2-1) operations which is O(n^2) complexity.

PS. Who ever decided the canonical answer is using slopes knows very little about planar geometry. People invented homogeneous coordinates for points and lines in a plane for the exact reason of having to represent vertical lines and other degenerate situations.

Upvotes: 1

Related Questions