[Haskell-cafe] Re: combinatorial search with running bound

[Michael Mossey]

Hi Chung-chieh,

When you ask for a pair of boxes, "How closely can they be brought together 
without intersection?" that provides a lower bound on the question "How 
closely can the groups be brought together?" (I.e. for that pair of boxes, 
bring them any closer and they intersect, so it is a lower bound.) The 
maximum of all these lower bounds in the minimum needed separation.

-Mike

Chung-chieh Shan wrote:
> Michael Mossey <mpm at alumni.caltech.edu> wrote in article <3942.75.50.175.130.1253997756.squirrel at mail.alumni.caltech.edu> in gmane.comp.lang.haskell.cafe:
>> The problem is to determine how closely the groups can be brought together
>> without any boxes intersection.
>>
>> The basic algorithm is to consider each pair of boxes and ask if they
>> have any "vertical overlap"---if so, figure out how closely they can be
>> brought together without intersecting, otherwise ignore them. Then take
>> the maximum of those numbers.
> 
> Wouldn't you mean minimum instead of maximum then?
> 
> I suspect that your code would be clearer without using a state monad.
>