CODEWITHSUNDEEP
algorithmdata-structuresgeometry
Rohan Monga
Rohan Monga

Reputation: 1777

Maximum Collinear points in a plane

N points are given as input.

Let's say (x1,y1), (x2,y2)... (xn,yn).

Is there a non-combinatorial solution to find the maximum number of collinear points? Can they be arranged in a fancy data structure that would help this computation?

Upvotes: 5

Views: 8195

Answers (3)

shintu
shintu

Reputation: 1

Following could be one way to solve it: 1) Find all the slopes selecting C(n,2) pairs 2) Bin these slopes into multiple buckets. 3) Within these buckets find independent lines (as they might contain family of parallel lines) 4) Establish the longest line segment

More concretely: 1) Perform (n-1) * (n-1) calculations to find so many slopes. A map could be used to save these points with slopes as keys. The value in the map could be a represented using a Set. The Set could contain an object representing two points. Something like this: {slope1: [(p1, p2), (p1, p3), (p1, p2), (p4, p5)]} {slope2: ....}

2) Now, within each set of points find independent lines. I believe iterating over each point in the set we can arrive at this. For example while visiting (p1, p2), (p1, p3), (p1, p2), (p4, p5) we can divide this into n-Sets which form collinear points. Set could start with: [p1, p2], when we encounter next pair (p1, p3), we check if either of them are already in the current running set. If at least one of them are then we add the new points to this set, otherwise create a new set. After iterating over all the points in this set of points we will have the following two sets, representing 2 independent line segments: [p1, p2, p3] [p4, p5] Size of these could now be used to establish the longest line segment we find

Complexity wise, it should be O((n-1)*(n-1) + n) ~ O(n^2). Assuming looking up objects in Set is O(1)

Upvotes: 0

Johan Kotlinski
Johan Kotlinski

Reputation: 25769

For each point i, find the slope to every other point j and look for duplicates. Duplicates can be found by sorting the slopes and comparing adjacent values. Point i is collinear with the points in each set of duplicates. Keep track of the maximal set as you go.

For each i, you have n-1 slopes to calculate and sort and compare. Therefore, using a (n log n) sorting, the complexity of the algorithm is O(n^2 log n).

Upvotes: 9

Rohit J
Rohit J

Reputation:

Read through discussion on this question here on

Upvotes: 1

Related Questions