Given a set of points in a cartesian plane, and a start point , find the k closest points to the starting point.
Points = [(1,2),(2,3),(4,6),(7,9)]
Start Point = (2,2)
Find 2 closest points to start point.
@vaddirajesh Welcome to the new Discuss! If applicable, could you please add company to the tags section? Please see here for instructions on how to do so, thanks.
@xidui said in K closest points to a starting point in cartesian plane:
And a set with of k to find the top k.
What do you mean by a set with of k? How do you determine which k points to insert into the set?
@1337c0d3r
sorry, It's size of k. I missed a word.
The top of the set records the largest number in the set.
If a new number come larger than the top, just discard it.
If a new number is smaller than the top, drop the top and insert the new one.
@xidui What if there are two points with the same distance from the start point? Then your set will only record one of them.
@xidui Yes it should work. I think a heap (or priority_queue
in C++) is more suitable, since you only access the top element.
What are the constraints of the problem? Are there many queries for different K?
If problem is isolated one, you have a set of points, and fixed start point, the approach above is very optimal.
But if we have a set of points and a lot of queries , where start point , K change, maybe it is better to use Kd tree for 2d. With Kd tree time complexity is klog(n) for query and nlog(n) for building the tree.Space complexity O(n).With Kd tree we don't need even to calculate euclidean distance
@elmirap Actually this problem is similar to finding Kth largest element in an array, which you can use the Selection algorithm to find the top K elements in O(n) time. However it is a non-trivial algorithm.
@elmirap This is a great follow up! If there are a lot of queries where start point or value of k change, or even when the set of points can be added, then solving it efficiently should use space partitioning algorithms like kd-tree to reduce the search space to a section in the cartesian space.
Tried using Max Heap. Please let me know if you think this would work.
Example array:
Points =[(1,2),(3,5),(6,5),(1,1)] , k =2 (Example executed.)
public class Points implements Comparable<Points>{
public double x;
public double y;
public Points(final double x, final double y){
this.x = x;
this.y = y;
}
public double getDist(){
return x*x+y*y;
}
@Override
public int compareTo(Points obj) {
int c = Double.compare(getDist(),obj.getDist());
if(c == 0){
c = Double.compare(x, obj.x);
if(c==0){
c = Double.compare(y, obj.y);
}
}
return c;
}
public void printData(){
System.out.print("x:"+ this.x+" "+"y:"+ this.y);
}
public class KClosestPointToOrigin {
public Points[] getClosestK(Points[]arr,int k){
PriorityQueue<Points> pq = new PriorityQueue <>(k,Collections.reverseOrder());
for(int i=0; i<arr.length; i++){
if(pq.size()<k){
pq.offer(arr[i]);
}else if(arr[i].getDist()<pq.peek().getDist()){
pq.remove();
pq.offer(arr[i]);
}
}
return pq.toArray(new Points[k]);
}
}
I think you can just use a max heap with a Point class,
Here is my example to find the closest point to <0,0>, same thing, just add one more parameter as the start point
The point class:
class Point{
int x;
int y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
public List<Point> closest(List<Point> points, int k){
List<Point> result = new ArrayList<>();
PriorityQueue<Point> maxHeap = new PriorityQueue<>(k, new Comparator<Point>() {
@Override
public int compare(Point p1, Point p2){
double d1 = getDistance(p1);
double d2 = getDistance(p2);
if(d1 == d2){
return 0;
}
return d1 < d2 ? 1 : -1;
}
});
//Traverse all the points in the list and find out the ones
for(int i = 0; i < points.size(); i++){
if(i < k){
maxHeap.offer(points.get(i));
} else if(getDistance(points.get(i)) < getDistance(maxHeap.peek())){
maxHeap.poll();
maxHeap.offer(points.get(i));
}
}
for(Point p : maxHeap){
result.add(p);
}
return result;
}
private double getDistance(Point p){
return Math.sqrt(p.x * p.x + p.y * p.y);
}