Skip to main content

Two Closest Points in plane


Set of points, the points closest to each other

Given a set of points in a x and y coordinates, find the pairs of points (x1, y1) (x2, y2) that are closest.

Algorithm will be used plane sweep and data structure will be 2-4 tree.
d - minimum distance between the so-far found closest points.
p is current point.
D is the ordered set of points present in strip.
  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.

Algorithm given http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html
2-4 tree link is http://www.cs.mcgill.ca/~cs251/ClosestPair/2-4trees.html.

Comments

Post a Comment

Popular posts from this blog

Car Parking Problem

There is n parking slots and n-1 car already parked. Lets say car parked with initial arrangement and we want to make the car to be parked to some other arrangement. Lets say n = 5, inital = free, 3, 4, 1, 2 desired = 1, free, 2, 4 ,3 Give an algorithm with minimum steps needed to get desired arrangement. Told by one of my friend and after a lot of search i really got a nice solution. I will post solution in comment part
3 comments
Read more

Median of Five Numbers

U have 5 NOs , X1,X2,X3,X4,X5 With minimum no. of comparisons we have to find a median. SWAP(X,Y) function is available to u . I have a answer of six comparisons and eight swaps....wait for people to find out by themselves.
1 comment
Read more

Merge two sorted array inplace

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space]. e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]
2 comments
Read more