Re: Algorithm to fit rectangles with different areas inside a matrix with lowest complexity

Hi Jacko,

Thanks for replying. The problem in my view, as I commented in Chris'
reply, is how to know which is the object with smallest growth impact.
Because in general if object 1 is bigger than object 2 under one rule
this is not telling me anything about their relation in another rule,
then when 2 objects collide and I place one of then I have to evaluate
all the possibilities that happen from that point on, i.e the other
object could collide with another one and new possibilities appear.

In my view is like a tree, where the root is the allocation where all
the objects are allocated according to rule 1. When N objects want to
be allocated in a place and they do not fit, then m new branches appear
in the tree, where m accounts for all the possible allocations of the
contending objects in that place. At every branch in the tree we can
associate the area that is allocated if we take that branch.

The optimum algorithm would be the one that is able to find in this
tree the path that results in the smallest area at the end (adding the
area allocated in every brach). For doing that I think it is needed a
criteria or indication every time that a node with multiple branches
appear to decide which is the branch that with most probability will
lead to the smallest area at the end. That is what I was trying to do
defining assumption (1) in the previous post.

What do you think ?

BR

Dani



jacko wrote:
place all objects in a place where they are smallest. then jiggle for
smallest overlap
if collision of location occurs, relocate object with smallest growth
impact to second size. then jiggle

in this way all objects go through go through scaling.

jiggleing is best don through genetic algorithms a la PCB optimization.

cheers

.

Relevant Pages

  • Re: [RFC] Stacking bio support
    ... - If you don't do it (but rely on the fact that the initial allocation is ... Yes, I reallocate. ... rely on (out of tree) bio throttling to prevent the memalloc reserve ...
    (Linux-Kernel)
  • Re: [PATCH 1/1] network memory allocator.
    ... Original idea was to store meta information used for allocation in an ... But there seems to be still an AVL tree in there? ... than 40%) imrovements of the request rates (1600-1800 requests per ... reduced cache line ping-pongs, ...
    (Linux-Kernel)
  • Re: [PATCH 1/1] network memory allocator.
    ... Original idea was to store meta information used for allocation in an ... But there seems to be still an AVL tree in there? ... and small and big machines first. ... fragmentations and power-of-two overhead. ...
    (Linux-Kernel)
  • Re: size_t
    ... This contributes to reduced memory footprint, ... overloaded) the block size for a single memory allocation is 8 bytes. ... tree (if it is on std::map implementations all more the power to the ...
    (comp.lang.cpp)