CareerCup

Find all the slopes for every pair on the plane which is N^2 algorithm. The slope that occurs the most would form the line that intersects the most points. Can anyone think of a better algorithm?

Not really sure how hough transform works here.

Apparently (from what I have read: here is a link: http://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm) the algorithm works by guessing discrete values for the parameters and checking for some sort of a fit. How is that linear time for this problem? Because of the discrete step guesses, we might even miss out on some lines.

I don't see how that applies here. Someone care to explain?

hough transform is the way to go...
basically every 2d point maps to a curve in hough parameter space...
we discretize the hough parameter space to MxN
if we have K points,
then enumerating all points take O(KN) time,
we find the max at the parameter space(this can be done in no time while enumerating)
so overall, it's linear!

Use a hash-table with (slope,intercept) pair as key and numPoint as value. Each (slope,intercept) key will have many points. Constructing this hash-table will take O(n^2) time, where n = num of points. Finding the (slope,intercept) with maximum number of points will be done by iterating over the hash-table. Boundary case of slope = infinity needs to be tackled separately.

This is actually a typical question solved by RANSAC
Search for RANSAC in wikipedia

if you were to use the slope , you must also take the base. So you actually hash to y=sx+b. Where s,b is your key. The value is the occ.

I realize that its hard to have a graph of the points in a line.. It is not so easy to construct. So this is like if you have the data structure precomputed already.

Hough transform ?

Sounds like linear regression problem. Principal component analysis (PCA) may help if that is the case. Find the first component!

hw do u hash it on 2 keys anythingyouwant??
a map allows for only 1 value as key.. an object may do for the value thingy? ..

let me know if m missing out sth..

Hough Transform works here in linear time

http://en.wikipedia.org/wiki/Hough_transform

This is what I found
http://mathpages.com/home/kmath110.htm

This is actually a typical question solved by RANSAC
Search for RANSAC in wikipedia

eigen analysis? take the largest eigenvector of the covariance matrix, maximizes the variance.

is this a math problem or a coding problem??? Software developer is supposed to know all stupid math stuff too :O

For 400 points

<pre lang="java" line="1" title="CodeMonkey82753" class="run-this">import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Random;

class Plane {
ArrayList<Point> itsPoints;

public Plane() {
randomPoints();
}

private void randomPoints() {
Random r = new Random();
itsPoints= new ArrayList<Point>();
char c = 'A';
for (int i=0;i<400;i++)
{
double x = r.nextDouble() * 1000;
double y = r.nextDouble() * 1000;
itsPoints.add(new Point(x, y,c));
c++;
}
}

public Plane(ArrayList<Point> thePoints) {
itsPoints = thePoints;
}

public LinkedHashSet<Point> getColinearPoints()
{
HashMap<Line, LinkedHashSet<Point>> aMap = new HashMap<Line, LinkedHashSet<Point>>();
Line result=null;
int max=0;
for(int i=0;i<itsPoints.size();i++)
{
Point a = itsPoints.get(i);
for(int j=i+1;j<itsPoints.size();j++)
{
Point b =itsPoints.get(j);
Line aLine = new Line(a, b);
LinkedHashSet<Point> points;
if(aMap.containsKey(aLine))
{
points = aMap.get(aLine);
points.add(a);
points.add(b);
}
else
{
points = new LinkedHashSet<Point>();
points.add(a);
points.add(b);
aMap.put(aLine,points);
}
if(points.size()>max){
max= points.size();
result=aLine;
}
}
}

return aMap.get(result);
}
}
class Point {
public double x;
public double y;
public char name;

public Point(double x, double y,char name) {
this.x = x;
this.y = y;
this.name = name;
}
}

class Line {

public double yIntercept;
public double slope;
public double episilon=0.0001;
public boolean isInfinity=false;
public Line(Point a,Point b)
{
double dx = b.x-a.x;
double dy = b.y-a.y;
if(Math.abs(dx)<=episilon)
{
isInfinity=true;
}
else
{
slope = dy/dx;
yIntercept = b.y - slope * b.x;
}
}
private boolean isEqual(Line theLine)
{
double dslope = Math.abs(theLine.slope-this.slope);
double dInt = Math.abs(theLine.yIntercept-this.yIntercept);
if(dslope <= episilon && dInt <=episilon)
return true;

return false;
}
@Override
public boolean equals(Object obj) {
// TODO Auto-generated method stub
Line aLine = (Line)obj;
if(aLine.isInfinity==this.isInfinity && isEqual(aLine))
return true;
return false;

}
@Override
public int hashCode() {
// TODO Auto-generated method stub
int a =(int) (1000*yIntercept);
int b = (int) (1000*slope);
return a | b ;
}

}
class Driver {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Plane aPlane = new Plane();
LinkedHashSet<Point> x = aPlane.getColinearPoints();
for(Point p:x)
{
System.out.print("{"+p.x+","+p.y+"}");
System.out.print(",");
}
}

}
</pre><pre title="CodeMonkey82753" input="yes">1
2
10
42
11

</pre>

this is regression problem for let's take
w^tx = b is equation of line. Now iteratively, start adjusting line w.

I think I have an O(n^2) soution.
There are n points.

1) consider n^2 combination of two points. calculate the slope of the pair of points and put the slope vs list of pair of points in a hashmap
ex. HashMap<Slope (double), ArrayList<Pair of points>>
2) so all the maximum number of points that fall on the same line should be in the same slope-arraylist map entry
3) For every map entry's list of points - check how many points fall on the same line using the line equation

O(n^2) solution:

public Line getLine(Point[] points) {
int length = points.length;
int max = 0;
Double maxSlope = 0.0;
Point maxPoint = null;
for (int i = 0; i < length; ++i) {
Point point = points[i];
HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
for (int j = 0; j < length; ++j) {
Point temp = points[j];
double slope = ((temp.y-point.y)*1.0)/(temp.x-point.x);
int count = 1;
if (hm.contains(slope)) {
	count += hm.get(slope);	
}
if (count > max) {
		max = count;
maxSlope = slope;
maxPoint = point;	
}
hm.put(slope, count);
}
 double maxConstant = maxPoint.y-maxSlope*maxPoint.x;
return new Line(maxSlope, maxConstant);
}

an O(N^2) approach, also works for duplicate points :
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:

int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}

void setSign(int &x,int &y){
if(x>0 && y>0) return;
if((x<0 && y<0) || (x>0 && y<0)){
x=-x;
y=-y;
return;
}

if(x==0){
if(y<0) y=-y;
return;
}
if(y==0){
if(x<0) x=-x;
return;
}
}

int maxPoints(vector<Point> &points) {
map<pair<int,int> ,int > slope;
map<pair<int,int>, int > ::iterator it;
int sum=0,ans=0;
for(int i=0;i<points.size();i++){
int dup=1; // for itself
slope.clear();
for(int j=0;j<points.size();j++){
if(i!=j){
if(!(points[i].x==points[j].x && points[i].y==points[j].y)){
int x=points[i].x-points[j].x;
int y=points[i].y-points[j].y;
setSign(x,y);
int g=gcd(x,y);
x/=g;
y/=g;
pair<int,int> p=make_pair(x,y);
it=slope.find(p);
if(it!=slope.end())
it->second++;
else
slope[p]=1;
}
else
dup++;
}
}
sum=0;
for(it=slope.begin();it!=slope.end();it++){
if(it->second > sum)
sum=it->second;
}
sum+=dup;
if(sum>ans)
ans=sum;
}
return ans;
}
};

what if you make the dfs out of it.. then it is O(v+e).. but then, again, you must construct that dfs.

for i=1:6000
  let m1=1, b1 = y[i]-x[i]*m1.
  let m1=2, b2 = y[i]-x[i]*m2.
  Calculate line of equation from (m1,b1), (m2,b2).

Now we have a set of 6000 lines. We compute the intersection point of these lines such that maximum line passes through this point. This can be done using line sweep algorithm.
Time complexity: O((N + K) log N) where K are the total number of points of intersection.

With respect to (0,0) find slope of every point. Hash < slope,<x,y>> and return maximum one. Time O(n).

the problem is a hard one.
but one can do it in O(n)