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

Question

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);
    }
}

Answer 1

I came to something very similar to @hqt's solution and want to elaborate on the details they've left out.

Two elements of this class are equal if their ratio dx to dy ratio (i.e., the slope) is the same.

static class Direction {
    Direction(Point p, Point q) {
        // handle anti-parallel via normalization
        // by making (dx, dy) lexicographically non-negative
        if (p.x > q.x) {
          dx = p.x - q.x;
          dy = p.y - q.y;
        } else if (p.x < q.x) {
          dx = q.x - p.x;
          dy = q.y - p.y;
        } else {
          dx = 0;
          dy = Math.abs(p.y - q.y);
        }
    }

    public boolean equals(Object obj) {
        if (obj==this) return true;
        if (!(obj instanceof Direction)) return false;
        final Direction other = (Direction) obj;
        return dx * other.dy == other.dx * dy; // avoid division
    }

    public int hashCode() {
        // pretty hacky, but round-off error is no problem here
        return dy==0 ? 42 : Float.floatToIntBits((float) dx / dy);
    }

    private final int dx, dy;
}

Now fill a Guava's Multimap<Direction, PointPair> by looping over all pairs (complexity O(n*n)). Iterate over all keys (i.e. directions) and process the List<PointPair> via a union find algorithm. The found partitions are sets of pairs of collinear points. If there are k collinear points, then you'll find a set containing all pairs of them.

Because of the union find algorithm, the complexity is O(n*n*log(n)), avoiding sorting didn't help.

Answer 2

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 :

1. 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.

2. 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.

Answer 3

Try Below

    //just to create random 15 points
    Random random = new Random();
    ArrayList<Point> points = new ArrayList<Point>();
    for(int i = 0; i < 15; i++){
        Point p = new Point(random.nextInt(3), random.nextInt(3));
        System.out.println("added x = " + p.x + " y = " + p.y);
        points.add(p);
    }

    //code to count max colinear points
    int p = 0;
    for(int i = 0; i < points.size() -1; i++){
        int colinear_with_x = 1;
        int colinear_with_y = 1;
        for(int j = i + 1; j < points.size(); j++){
            if(points.get(i).x == points.get(j).x){
                colinear_with_x++;
            }
            if(points.get(i).y == points.get(j).y){
                colinear_with_y++;
            }
        }
        p = max(p,colinear_with_x,colinear_with_y);
    }

Answer 4

An approach, that relies heavily on a good hashed map:

As key use the a linear equation (defining a line), so that you have a map along the line of

map<key=(vector, point), value=quantity> pointsOnLine

where vector and point define the linear function that two points determine.

Then you iterate over all n points:

maxPoints = 2
for i=1 to n
  for j=i+1 to n
    newKey = lineParametersFromPoints(point[i], point[j])
    if pointsOnLine.contains(newKey)
      pointsOnLine[key] += 1
      if maxPoints < pointsOnLine[key]
        maxPoints = pointsOnLine[key]
    else
      pointsOnLine.add(key)
      pointsOnLine[key] = 2

maxPoints then contains the maximum number of colinear points.

Please note (this is probably most important), that the hash-compare function of the map must check that the two lines represent the same linear function, even if the vectors are anti-parallel or the points on the two lines are not the same (but one satisfies the other equation).

This approach does of course heavily rely on the map having fast access and insertion times.