Optimize algorithm from O(n^3) to O(n^2)

algorithm, java, optimization

Solution

You can use angular coefficient between two points with Ox to solve this problem. For example, for 3 points : A B C. If they're collinear if and only if line AB and line AC make a same angular coefficient with Ox line. So, here is pseudocode of mine :

// Type : an object to store information to use later
List<Type> res = new ArrayList<Type>();  
for (int i = 0; i < points.lenght(); i++) {
    for (int j = i+1; j < points.length(); j++) {
       double coefficient = CoeffiecientBetweenTwoLine(
                   line(points[i], points[j]), line((0,0), (0,1));
       res.add(new Type(points[i], points[j], coefficient);
    }
}

After that, you use QuickSort, sort again above List base on Coefficient. And any coefficient equals, we can know which points are collinear. Complexity of this algorithm is `O(N^2logN)` (dominated by sorting a list with `O(N^2)` elements, only `O(N^2)` required to build the list).

@Edit: So how can we know how many points collinear when we show equal coefficient ? There are many ways to solve this problem.

At sort step, you can sort by first parameter (is which point in that line) when two coefficient are equal. For example. After sort, the result should be (in this case, if 1 3 and 4 are collinear) :

(1 3) (1 4) (3 4)

From above building, you just need to see streak of 1. in this example, is 2. so the result should be 3. (always k + 1)

- Use formula : because number of pair that equals always : `n*(n-1)/2` . So, you will have : `n*(n-1)/2 = 3`. and you can know n = 3 (n >= 0). That means you can solve quadratic equation here (but not too difficult, because you always know it have solution, and just get one solution that positive)

Edit 2 Above step to know how many collinear points is not true, because at case for example, A B and C D are two parallel line (and line AB is different from line CD), the result, they still have same coefficient with Ox. So, I think to fix this problem, you can use `Union-Find` Data structure to solve this problem. Step will be :

Sort again angular coefficient For example : (1 2 3 4) is collinear and they're parallel with (5,6,7) and point 8 stands somewhere else. So, after sort, the result should be :

(1 2) (1 3) (1 4) (2 3) (2 4) (5 6) (5,7) (6,7) angular coefficient equals, but at two different line

(1,5) (1, 6) .. // Will have some pair connect between two set of parallel line. (1, 8)

(5, 8) (3, 8) .... // Random order. because don't know.

Use Union-Find Data structure to join tree: Start iterate from second element, if you see its angular coefficient equals with previous, join itself and join previous. For example,

(1,3) == (1,2) : join 1 and 2, join 1 and 3.

(1,4) == (1,3) : join 1 and 3, join 1 and 4. ....

(5,6) : join 2 and 4, join 5 and 6.

(5,7): join 5 and 7, join 5 and 6 ...

(1,8) : not join anything. (5,8) : not join anything ...

After you finish this step. All you have is a multi-tree, in each tree, is a set of points that they're collinear.

Above step, you see that some pairs are join multi-time. you can simply fix this by mark, if they're already join, ignore to enhance more in performance.

@ : I think this solution is not good, I just do by my brain-thinking, not a real algorithm behind. So, any other clear ideas, please tell me.

Problem

The problem I am trying to solve is as follows: Assume you are given set of points in a two dimensional space and how can we get maximum number of colinear points. I did the problem in Java. First I created a method that checks for linearity: ``` return (y1 - y2) * (x1 - x3) = (y1 - y3) * (x1 - x2); ``` Then I used three `for` loops which makes my algorithm O(n^3). But I am trying to see if this can be reduce to O(n^2). After searching on the net I found that my implementation is very similar to whats here. So the question is how can we improve the complexity. Any example would be great. This is what I ended up doing: ``` int p = 2; for (int i = 0; i < points.lenght(); i++) { for (int j = i+1; j < points.length(); j++) { int count = 2; for (int k =0; i < points.length(); k++) { if (k == i || k == j) continue; //use linearity function to check if they are linear... } p = max(p,count); } } ```

Original source