Author |
Topic: Select points (Read 8310 times) |
|
birbal
Full Member
Gender:
Posts: 250
|
|
Select points
« on: Dec 3rd, 2012, 11:26am » |
Quote Modify
|
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.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Select points
« Reply #1 on: Dec 3rd, 2012, 1:32pm » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wiley
Newbie
Posts: 12
|
|
Re: Select points
« Reply #2 on: Dec 5th, 2012, 9:21am » |
Quote Modify
|
Could you please explain your both solutions in more detail. With DP, are you thinking of brute-force algo and leveraging DP to avoid re-calculation of sub-problems?
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #3 on: Dec 11th, 2012, 2:37am » |
Quote Modify
|
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 ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Select points
« Reply #4 on: Dec 11th, 2012, 9:17am » |
Quote Modify
|
on Dec 11th, 2012, 2:37am, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #5 on: Dec 11th, 2012, 9:53am » |
Quote Modify
|
on Dec 11th, 2012, 9:17am, 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 ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Select points
« Reply #6 on: Dec 11th, 2012, 10:27am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #7 on: Dec 11th, 2012, 10:47am » |
Quote Modify
|
on Dec 11th, 2012, 10:27am, 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.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #8 on: Dec 13th, 2012, 10:49am » |
Quote Modify
|
on Dec 3rd, 2012, 1:32pm, 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 ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Select points
« Reply #9 on: Dec 13th, 2012, 11:45am » |
Quote Modify
|
on Dec 13th, 2012, 10:49am, 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..
|
« Last Edit: Dec 13th, 2012, 11:45am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #10 on: Dec 15th, 2012, 1:00pm » |
Quote Modify
|
on Dec 13th, 2012, 11:45am, towr wrote: 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.. |
| Can you explain in more detail? What is a,b,c and minarg b: ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Select points
« Reply #11 on: Dec 15th, 2012, 1:32pm » |
Quote Modify
|
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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #12 on: Dec 23rd, 2012, 6:10am » |
Quote Modify
|
Code:int SelectPoints(int *points, int n, int m) { int *maxDist = new int [n]; for(int i=1; i<n; i++) { maxDist[i] = points[i] - points[0]; } for(int i=3; i<=m; i++) { for(int j=n-1; j >= 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?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Select points
« Reply #13 on: Dec 23rd, 2012, 4:30pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #14 on: Dec 23rd, 2012, 8:16pm » |
Quote Modify
|
on Dec 23rd, 2012, 4:30pm, 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..
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #15 on: Dec 23rd, 2012, 8:18pm » |
Quote Modify
|
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<m; i++) { maxDist[i] = points[i] - points[0]; } for(int i=3; i<=n; i++) { for(int j=m-1; j >= 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]; } |
|
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Select points
« Reply #16 on: Dec 24th, 2012, 3:59am » |
Quote Modify
|
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.
|
« Last Edit: Dec 24th, 2012, 3:59am by Grimbal » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #17 on: Dec 24th, 2012, 8:46am » |
Quote Modify
|
on Dec 24th, 2012, 3:59am, 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.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Select points
« Reply #18 on: Dec 24th, 2012, 10:41am » |
Quote Modify
|
I don't think this idea will ever be as efficient as the other approach.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Select points
« Reply #19 on: Dec 24th, 2012, 12:05pm » |
Quote Modify
|
on Dec 24th, 2012, 10:41am, 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
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Select points
« Reply #20 on: Dec 24th, 2012, 1:06pm » |
Quote Modify
|
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; |
|
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|