wu :: forums - Print Page


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

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

Title: Select points
Post by birbal on Dec 3^rd, 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 3^rd, 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 5^th, 2012, 9:21am

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?

Title: Re: Select points
Post by birbal on Dec 11^th, 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 11^th, 2012, 9:17am

on 12/11/12 at 02:37:09, birbal 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)

Title: Re: Select points
Post by birbal on Dec 11^th, 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 11^th, 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 11^th, 2012, 10:47am

on 12/11/12 at 10:27:59, towr wrote:

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 13^th, 2012, 10:49am

on 12/03/12 at 13:32:55, towr wrote:

What is the DP solution for this ?

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

on 12/13/12 at 10:49:58, birbal wrote:

What is the DP solution for this ?

min_spacing([a..c]) = minarg_{b: 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 15^th, 2012, 1:00pm

on 12/13/12 at 11:45:08, towr wrote:

min_spacing([a..c]) = minarg_{b: 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: ?

Title: Re: Select points
Post by towr on Dec 15^th, 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 23^rd, 2012, 6:10am

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?

Title: Re: Select points
Post by Grimbal on Dec 23^rd, 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 23^rd, 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 23^rd, 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<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];
}

Title: Re: Select points
Post by Grimbal on Dec 24^th, 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 24^th, 2012, 8:46am

on 12/24/12 at 03:59:18, Grimbal wrote:

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 24^th, 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 24^th, 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 24^th, 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;