Author |
Topic: Select points (Read 8284 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print