CODEWITHSUNDEEP
performancealgorithmmathlanguage-agnostic
Spandan
Spandan

Reputation: 2138

Find K nearest Points to Point P in 2-dimensional plane

Source: AMAZON INTERVIEW QUESTION

Given a point P and other N points in two dimensional space, find K points out of the N points which are nearest to P.

What is the most optimal way to do this ?

This Wiki page does not provide much of help in building a algorithm.Any ideas/approaches people.

Upvotes: 26

Views: 36147

Answers (9)

havij
havij

Reputation: 1170

C# Solution using LINQ

public int[][] KClosest(int[][] points, int[][] p, int K) {

    var orderedPoints = points.OrderBy(point => Math.Pow(point[0]-p[0], 2) + Math.Pow(point[1]-p[1], 2));
    return orderedPoints.Take(K).ToArray();
}

Upvotes: 0

NishiKant Goutam
NishiKant Goutam

Reputation: 1

public static void NearestPoints() {
    int[][] Points = { new int[] { -16, 5 },
                       new int[] { -1, 2 },
                       new int[] { 4, 3 },
                       new int[] { 10, -2 },
                       new int[] { 0, 3 },
                       new int[] {- 5, -9 } };
    // Linq Order by default use quick sort which will be best suited in this.
    var orderPoint = from i in Enumerable.Range(0, Points.Length)
                     orderby Math.Sqrt( Points[i][0] * Points[i][0] 
                                         + Points[i][1] * Points[i][1] )
                     select new int[][] { Points[i] };
    var result = orderPoint.Take(3);
}

Upvotes: -2

issam
issam

Reputation: 93

class Solution {
   public int[][] kClosest(int[][] points, int K) {
        double [] combinationArr = new double[points.length];
        Hashtable<Double,int[]> pt = new Hashtable();
        for (int i = 0; i <points.length; i++) {
            int [] in = points[i];
            for (int j = 0; j < in.length - 1; j++) {
                Integer x = in[j];
                Integer y = in[j + 1];

                double powerX=Math.pow(x, 2);
                double powerY = Math.pow(y, 2);
                double combination= (Double)(Math.sqrt(powerX + powerY));
                pt.put(combination, points[i]);
                combinationArr[i] = combination;
            }

        }

        Arrays.sort(combinationArr);
        int [][] kpoints = new int[K][K];
        for (int n = 0; n < K; n++) {
            kpoints[n] = pt.get(combinationArr[n]);
        }
       return kpoints;
}
}

Upvotes: 0

Catriel
Catriel

Reputation: 647

// point_type pt, length_sq(p) { return pt[0] * pt[0] + pt[1] * pt[1]}
// std::vector<point_type> points to search.
// The algorithm should recursion depth to 
//       O(k * log(points.size())), and
// running time to O(points.size()).

std::nth_element(
               points.begin(),
               points.begin() + k,
               points.end(),
               [&pt](point_type const & a)
               {
                    return length_squared(a - pt);
               });

// points[0], ... , points[k - 1] are the closest points to pt

Upvotes: 0

hotpro
hotpro

Reputation: 336

Solution 1

private List<Point> nearestKPoint_1(List<Point> list, final Point center, int k) {
    List<Point> ans = new ArrayList<>();
    PriorityQueue<Point> maxHeap = new PriorityQueue<>(k + 1, new Comparator<Point>() {
        @Override
        public int compare(Point o1, Point o2) {
            return distance(center, o2) - distance(center, o1);
        }
    });
    for (Point p : list) {
        maxHeap.offer(p);
        if (maxHeap.size() > k) {
            maxHeap.poll();
        }
    }
    Iterator<Point> i = maxHeap.iterator();
    while (i.hasNext()) {
        ans.add(i.next());
    }
    return ans;
}

public int distance(Point p1, Point p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

static class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Point point = (Point) o;

        if (x != point.x) return false;
        return y == point.y;
    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }
}

Solution 2

private List<Point> nearestKPoint_2(List<Point> list, final Point center, int k) {
    List<Point> ans = new ArrayList<>();
    Distance[] nums = new Distance[list.size()];
    for (int i = 0; i < nums.length; i++) {
        nums[i] = new Distance(distance(center, list.get(i)), i);
    }
    quickSelect(nums, k);
    for (int i = 0; i < k; i++) {
        ans.add(list.get(nums[i].i));
    }
    return ans;
}

private void quickSelect(Distance[] nums, int k) {
    int start = 0, end = nums.length - 1;
    while (start < end) {
        int p = partition(nums, start, end);
        if (p == k) {
            return;
        } else if (p < k) {
            start = p + 1;
        } else {
            end = p - 1;
        }
    }
}
private int partition(Distance[] nums, int start, int end) {
    Distance pivot = nums[start];
    int i = start, j = end + 1;
    while (true) {
        while (i < end && nums[++i].compareTo(pivot) < 0);
        while (j > start && nums[--j].compareTo(pivot) > 0);
        if (i >= j) {
            break;
        }
        swap(nums, i, j);
    }
    swap(nums, start, j);
    return j;
}

private void swap(Distance[] nums, int i, int j) {
    Distance tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

class Distance implements Comparable<Distance> {
    int d;
    int i;

    public Distance(int d, int i) {
        this.d = d;
        this.i = i;
    }

    @Override
    public int compareTo(Distance o) {
        return this.d - o.d;
    }
}

Upvotes: 5

Harshit
Harshit

Reputation: 692

What is wrong with below approach ?

1) Calculate distance from given point to other points.

2) Store the distance and index of that point to TreeMap<Double,Integer> map

3) Select top K elements from map. It's values will give index of Point element from points array.

The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time,

Upvotes: -1

fury
fury

Reputation: 95

You could use KD tree http://en.wikipedia.org/wiki/K-d_tree to partition space and given the point you will be able to gradually search for neighbors using binary search. Benefit of using this approach is that it easily scales up to online version when you receive points/queries in runtime one by one or in batches.

Upvotes: 4

Анатолий
Анатолий

Reputation: 2857

Solution 1 make heap of size K and collect points by minimal distance O(NLogK) complexity.

Solution 2: Take and array of size N and Sort by distance. Should be used QuickSort (Hoare modification). As answer take first K points. This is too NlogN complexity but it is possible optimize to approximate O(N). If skip sorting of unnecessary sub arrays. When you split array by 2 sub arrays you should take only array where Kth index located. complexity will be : N +N/2 +N/4 + ... = O(N).

Solution 3: search Kth element in result array and takes all point lesser then founded. Exists O(N) alghoritm, similar to search of median.

Notes: better use sqr of distance to avoid of sqrt operations, it will be greater faster if point has integer coordinates.

As interview answer better use Solution 2 or 3.

Upvotes: 39

Bernhard Barker
Bernhard Barker

Reputation: 55609

For just a single query...

Maintain a heap of size k.

For each point, calculate the distance to the point P. Insert that distance into the heap and delete the maximum from the heap if the size of the heap is greater than k.

Running time: O(n log k)

Upvotes: 8

Related Questions