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

Michael Mossey mpm at alumni.caltech.edu
Tue Sep 29 00:09:32 EDT 2009

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.


Chung-chieh Shan wrote:
> Michael Mossey <mpm at alumni.caltech.edu> wrote in article <3942. 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.

More information about the Haskell-Cafe mailing list