K closest points to a starting point in cartesian plane


  • 2
    V

    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.


  • 0

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


  • 0

    Calculate all the distance with O(n) seems unavoidable.
    And a set with size of k to find the top k.

    Is there some more idea?


  • 0

    @xidui What is the complexity?


  • 0

    @1337c0d3r
    Time complexity: O(n) + O(n * logk)
    Space complexity: O(k)


  • 0

    @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?


  • 0

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


  • 0

    @xidui What if there are two points with the same distance from the start point? Then your set will only record one of them.


  • 0

    @1337c0d3r
    how about multiset? I think this can work.


  • 1

    @xidui Yes it should work. I think a heap (or priority_queue in C++) is more suitable, since you only access the top element.


  • 0

    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


  • 0

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


  • 0

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


  • 0
    C

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

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.