K closest points in two dimension array
You are given a set of points, made up of x and y coordinates. You are also provide with a reference point.
Write a function that finds and return the k closest points to the reference point.
Assume the k can be up on serveral hundreds and allPoints is in the order of millions.
What is the runtime complexity of your solutions?
// Compile: javac KClosestPoint.java and java KClosestPoint
// Runtime: (n*logk)
class Point{
double x;
double y;
public Point(double x, double y){
this.x = x;
this.y = y;
}
}

class Distance implements Comparable<Distance>{
Point ref;
Point point;
public Distance(Point ref, Point point){
this.ref = ref;
this.point = point;
}

private double norm(){
double normRef = (point.x - ref.x)*(point.x - ref.x) +
(point.y - ref.y)*(point.y - ref.y);
return normRef;
}
public int compareTo(Distance d){
if(this.norm() > d.norm())
return 1;
else if(this.norm() == d.norm() )
return 0;
else
return -1;

}
public String toString(){
return "["+ point.x +"]["+ point.y +"]";
}
}

public class KClosestPoint {
public static void main(String[] args) {
test1();
}
public static void test1() {

Point ref = new Point(1, 1);
Set<Point> set = new HashSet<Point>();

PriorityQueue<Distance> queue = new PriorityQueue<Distance>();
for(Point pt : set){
}
int k = 3;
while(k > 0){
System.out.println(queue.remove().toString());
k--;
}
}
}