```

wu :: forums
(http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)

riddles >> cs >> Select points
(Message started by: birbal on Dec 3rd, 2012, 11:26am)

```

Title: Select points
Post by birbal on Dec 3rd, 2012, 11:26am
Given a 1-D space and m point on it. Task is to select n point (n <= m) such that minimum distance between any two of the selected points is maximized.

Title: Re: Select points
Post by towr on Dec 3rd, 2012, 1:32pm
Why say a "1-D space", when you can say a "line" ?

There's a number of ways to approach it; dynamic programming should work.
Or you could do a binary search for the minimal distance, by seeing if for a given distance you can find m points so distanced (which you can do greedily). You can make a first estimate based on the maximum and minimum.

The problem sounds like something I've seen on the forum before..

Title: Re: Select points
Post by wiley on Dec 5th, 2012, 9:21am
With DP, are you thinking of brute-force algo and leveraging DP to avoid re-calculation of sub-problems?

Title: Re: Select points
Post by birbal on Dec 11th, 2012, 2:37am
Trying to solve this using binary search on distance range. The sub problem would be to find n points of the given m points such that minimum distance between any two points is k. How efficiently can we solve this problem ?

Title: Re: Select points
Post by towr on Dec 11th, 2012, 9:17am

on 12/11/12 at 02:37:09, birbal wrote:
 Trying to solve this using binary search on distance range. The sub problem would be to find n points of the given m points such that minimum distance between any two points is k. How efficiently can we solve this problem ?
At most linear, since you can just do it greedily. You could to this with binary search as well, in which case it'd be O(n log n)

Title: Re: Select points
Post by birbal on Dec 11th, 2012, 9:53am

on 12/11/12 at 09:17:47, towr wrote:
 At most linear, since you can just do it greedily. You could to this with binary search as well, in which case it'd be O(n log n)

I see...Start from first point, pick next point at a distance of >= k and repeat this until you find n points.
How can this be done by binary search ?

Title: Re: Select points
Post by towr on Dec 11th, 2012, 10:27am
If your current point is x, you want to find the first element greater than or equal to x+k, so you just search for it with binary search.
Then you have to repeat that m times, to get all m points that are spaced at least k apart.

Title: Re: Select points
Post by birbal on Dec 11th, 2012, 10:47am

on 12/11/12 at 10:27:59, towr wrote:
 If your current point is x, you want to find the first element greater than or equal to x+k, so you just search for it with binary search. Then you have to repeat that m times, to get all m points that are spaced at least k apart.

Great....so this is O(n log n). Other approach could be (assuming points are sorted) If we are at any point x - keep moving until we find next point at least at x+k. For this approach we will need to go through all m points to find n points which are at least k distant.

Title: Re: Select points
Post by birbal on Dec 13th, 2012, 10:49am

on 12/03/12 at 13:32:55, towr wrote:
 Why say a "1-D space", when you can say a "line" ?There's a number of ways to approach it; dynamic programming should work. Or you could do a binary search for the minimal distance, by seeing if for a given distance you can find m points so distanced (which you can do greedily). You can make a first estimate based on the maximum and minimum.The problem sounds like something I've seen on the forum before..

What is the DP solution for this ?

Title: Re: Select points
Post by towr on Dec 13th, 2012, 11:45am

on 12/13/12 at 10:49:58, birbal wrote:
 What is the DP solution for this ?

min_spacing([a..c]) = minargb: a<b<c max( min_spacing([a...b]) , min_spacing([b...c])
So you should be able to build a table with partial results for it..

Title: Re: Select points
Post by birbal on Dec 15th, 2012, 1:00pm

on 12/13/12 at 11:45:08, towr wrote:
 min_spacing([a..c]) = minargb: a

Can you explain in more detail? What is a,b,c and minarg b: ?

Title: Re: Select points
Post by towr on Dec 15th, 2012, 1:32pm
a,b,c are points on the line; or equivalent elements in the (sorted) array that represent the points on the line.
The minarg thing might actually be an error, I think that's actually for finding the minimizing variable, whereas I do want to find the minimum. But I want to find the minimum for varying b. There may be multiple choices for a point b between a and c, and you want to find the one that gives the minimum spacing, which is the maximum of the minimum-spacing over a..b and b..c

Title: Re: Select points
Post by birbal on Dec 23rd, 2012, 6:10am

Code:
 int SelectPoints(int *points, int n, int m){int *maxDist = new int [n];for(int i=1; i= i-1; j--){int max = 0;for(int k = j-1; k >= i-2; k--){int temp = min(points[j] - points[k], maxDist[k]);if(temp > max){max = temp;}}maxDist[j] = max;}}return maxDist[n-1];}

Is this code doing the same?

Title: Re: Select points
Post by Grimbal on Dec 23rd, 2012, 4:30pm
I am not sure what you want to do, but it doesn't look too good.  You never consider point[j] - point[k] for j,k>n

Title: Re: Select points
Post by birbal on Dec 23rd, 2012, 8:16pm

on 12/23/12 at 16:30:01, Grimbal wrote:
 I am not sure what you want to do, but it doesn't look too good.  You never consider point[j] - point[k] for j,k>n

oops...i think i changed m to n and n to m. Read m as n and n as m, it will make sense.. :P

Title: Re: Select points
Post by birbal on Dec 23rd, 2012, 8:18pm
Rewriting code with correct m, n meaning.

Code:
 int SelectPoints(int *points, int n, int m) { int *maxDist = new int [m]; for(int i=1; i= i-1; j--) { int max = 0; for(int k = j-1; k >= i-2; k--) { int temp = min(points[j] - points[k], maxDist[k]); if(temp > max) { max = temp; } } maxDist[j] = max; } } return maxDist[m-1]; }

Title: Re: Select points
Post by Grimbal on Dec 24th, 2012, 3:59am
In the meantime I realized you just inverted n and m.  It looks correct to me.

If I understand towr's idea correctly, it is not exactly the same.  Towr splits the problem in 2 halves and searches the optimal point b where to cut it.  You do the same, but on the right side you add a single interval.

Note that the optimal k can be found faster.  As k increases, maxDist[k] increases but point[j]-point[j] decreases.  So you could search the best k with a binary search.  Or maybe you could search sequentially from the optimal k you found for the previous value of j.  It shouldn't be far.

Title: Re: Select points
Post by birbal on Dec 24th, 2012, 8:46am

on 12/24/12 at 03:59:18, Grimbal wrote:
 In the meantime I realized you just inverted n and m.  It looks correct to me.If I understand towr's idea correctly, it is not exactly the same.  Towr splits the problem in 2 halves and searches the optimal point b where to cut it.  You do the same, but on the right side you add a single interval.Note that the optimal k can be found faster.  As k increases, maxDist[k] increases but point[j]-point[j] decreases.  So you could search the best k with a binary search.  Or maybe you could search sequentially from the optimal k you found for the previous value of j.  It shouldn't be far.

Agreed. I did not pay attention to such optimisation, was just trying to convert idea to code. :)

Title: Re: Select points
Post by towr on Dec 24th, 2012, 10:41am
I don't think this idea will ever be as efficient as the other approach.

Title: Re: Select points
Post by birbal on Dec 24th, 2012, 12:05pm

on 12/24/12 at 10:41:08, towr wrote:
 I don't think this idea will ever be as efficient as the other approach.

Can you convert your idea to code? It will be better undertandable that way ;)

Title: Re: Select points
Post by towr on Dec 24th, 2012, 1:06pm
The following should give the gist of it (but it can probably be improved and there may be bugs.)

Python
Code:
 def findMaxMinDistance(points, m): upperlimit = round((points[-1]-points[0])/(m-1)); lowerlimit = upperlimit; for i in range(1, len(points)):  lowerlimit = min(lowerlimit, points[i]-points[i-1]); return findMaxMinDistanceBetween(points, m, lowerlimit, upperlimit);def findMaxMinDistanceBetween(points, m, lowerlimit, upperlimit): if lowerlimit >= upperlimit:   return upperlimit hdist = round((lowerlimit+upperlimit+1)/2); rdist = findPathMin(points, m, hdist); if rdist == -1:  return findMaxMinDistanceBetween(points, m, lowerlimit, hdist-1); else:  return findMaxMinDistanceBetween(points, m, rdist, upperlimit); def findPathMin(points, m, distance): prev = points[0]; nextEst = prev + distance; minDist = points[-1]; m -=1; for point in points[1:]:  if point >= nextEst:    minDist = min(minDist, point-prev)    m-=1;    prev = point    nextEst = prev + distance; if m <= 0:  return minDist; else:  return -1;