wu :: forums
« wu :: forums - Select points »

Welcome, Guest. Please Login or Register.
Oct 12th, 2024, 5:07pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: ThudnBlunder, Eigenray, Icarus, william wu, Grimbal, towr, SMQ)
   Select points
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Select points  (Read 8310 times)
birbal
Full Member
***





   


Gender: male
Posts: 250
Select points  
« on: Dec 3rd, 2012, 11:26am »
Quote Quote Modify 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: male
Posts: 13730
Re: Select points  
« Reply #1 on: Dec 3rd, 2012, 1:32pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 250
Re: Select points  
« Reply #3 on: Dec 11th, 2012, 2:37am »
Quote Quote Modify 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: male
Posts: 13730
Re: Select points  
« Reply #4 on: Dec 11th, 2012, 9:17am »
Quote Quote Modify 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: male
Posts: 250
Re: Select points  
« Reply #5 on: Dec 11th, 2012, 9:53am »
Quote Quote Modify 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: male
Posts: 13730
Re: Select points  
« Reply #6 on: Dec 11th, 2012, 10:27am »
Quote Quote Modify 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: male
Posts: 250
Re: Select points  
« Reply #7 on: Dec 11th, 2012, 10:47am »
Quote Quote Modify 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: male
Posts: 250
Re: Select points  
« Reply #8 on: Dec 13th, 2012, 10:49am »
Quote Quote Modify 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: male
Posts: 13730
Re: Select points  
« Reply #9 on: Dec 13th, 2012, 11:45am »
Quote Quote Modify 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: male
Posts: 250
Re: Select points  
« Reply #10 on: Dec 15th, 2012, 1:00pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Select points  
« Reply #11 on: Dec 15th, 2012, 1:32pm »
Quote Quote Modify 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: male
Posts: 250
Re: Select points  
« Reply #12 on: Dec 23rd, 2012, 6:10am »
Quote Quote Modify 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: male
Posts: 7527
Re: Select points  
« Reply #13 on: Dec 23rd, 2012, 4:30pm »
Quote Quote Modify 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: male
Posts: 250
Re: Select points  
« Reply #14 on: Dec 23rd, 2012, 8:16pm »
Quote Quote Modify 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.. Tongue
IP Logged

The only thing we have to fear is fear itself!
birbal
Full Member
***





   


Gender: male
Posts: 250
Re: Select points  
« Reply #15 on: Dec 23rd, 2012, 8:18pm »
Quote Quote Modify 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: male
Posts: 7527
Re: Select points  
« Reply #16 on: Dec 24th, 2012, 3:59am »
Quote Quote Modify 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: male
Posts: 250
Re: Select points  
« Reply #17 on: Dec 24th, 2012, 8:46am »
Quote Quote Modify 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. Smiley
 
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: male
Posts: 13730
Re: Select points  
« Reply #18 on: Dec 24th, 2012, 10:41am »
Quote Quote Modify 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: male
Posts: 250
Re: Select points  
« Reply #19 on: Dec 24th, 2012, 12:05pm »
Quote Quote Modify 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 Wink
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: male
Posts: 13730
Re: Select points  
« Reply #20 on: Dec 24th, 2012, 1:06pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board