Menu
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?
365
A line contains at least two points. If two lines intersect, then their intersection is exactly one point. Through any three non-collinear points, there exists exactly one plane. A plane contains at least three non-collinear points.
Three or more points are said to be collinear if the slope of any two pairs of points is the same.
Three non-collinear points determine a plane. This statement means that if you have three points not on one line, then only one specific plane can go through those points. The plane is determined by the three points because the points show you exactly where the plane is.
(xv) The maximum number of points of intersection of three lines is three.
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).
187
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
