closest pair problem

Closest pair of points problem on wiki

nearest neighbor problem

k-d tree on wiki

Sweeping: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPair1D.html

every time the sweep line encounters a point p, we will perform the following actions:

1. Remove the points further than d to the left of p from the ordered set D that is storing the points in the strip.  
2. Determine the point on the left of p that is closest to it
3. If the distance between this point and p is less than d (the current minimum distance), then update the closest current pair and d.

The summary and analysis of the plane sweep algorithm goes something like this:

• sort the set according to x-coordinates (this is necessary for a plane sweep approach to determine the coordinates of the next point), which takes O(nlogn) time
• inserting and removing each point once from the ordered set D (each insertion takes O(logn) time as shown in the section on (2,4)-trees), which takes a total of O(nlogn) time
• comparing each point to a constant number of its neighbors (which takes O(n) time in total )

K-D Tree

Animation: http://donar.umiacs.umd.edu/quadtree/points/kdtree.html

Complexity

• Building a static kd-tree from n points takes O(n log ² n) time if an O(n log n) sort is used to compute the median at each level. The complexity is O(n log n) if a linear median-finding algorithm such as the one described in Cormen et al^[3] is used.

• Inserting a new point into a balanced kd-tree takes O(log n) time.
• Removing a point from a balanced kd-tree takes O(log n) time.
• Querying an axis-parallel range in a balanced kd-tree takes O(n^1-1/d +k) time, where k is the number of the reported points, and d the dimension of the kd-tree.
• Finding the nearest point is an O(log N) operation.