

Title: Select points Post by birbal on Dec 3^{rd}, 2012, 11:26am Given a 1D 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 "1D 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 bruteforce algo and leveraging DP to avoid recalculation of subproblems? 

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:


Title: Re: Select points Post by birbal on Dec 11^{th}, 2012, 9:53am on 12/11/12 at 09:17:47, towr wrote:
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:
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:
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 minimumspacing over a..b and b..c 

Title: Re: Select points Post by birbal on Dec 23^{rd}, 2012, 6:10am Code:
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:
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:


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:
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:


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