# constraints placement question

Suppose I have a set of squares. I get them in iterative way – one after another.

I would like to place the squares in some structure according to set of rules:

When a new square arrives all squares which arrived before it are already placed. The new square arrives with dependency flag to one of squares, which was treated. The dependency flag can be L or R.

If the dependency is L and a new square i depends on j it can be placed:

If the dependency is R and a new square i depends on j it can be placed: Note: In general we have to use placement options the preferable placement is 1 if it is impossible 2 or 3 (2/3 have the same priorety) 4,5 are used only if it is impossible to use one of 1,2,3.

If j is totally surrounded by another squares i is placed "after" surrounding squares based on dependency flag.

The placement goal is to generate as compact a "mesh" as possible.

For example if squares arrive in the format: new_square, dependent_on_square, dependency_flag

And we have

1, NULL, NULL

2, 1, R

3, 2, R

4, 2, L

5, 4, L

6, 5, L

7, 6, L

8, 7, L

9, 8, L

It is possible to create two arrangement 1) compact 2) not compact

Definition for compact layout(placement):

If we will pad the acquired layout with empty squares ,in such a way that we will get rectangular the number of empty squares will be minimumal in obtained layout.

Note : The rectangular obtained as a result of padding shoud be as small as possible.

I mean that if the width if layout before padding is w the generated rectangular will be by width w.(The same regarding the height) .

Demonstartion in the above examples

Could someone propose an algorithm to do such kind of placement?

• @Yakov: The question is missing. – Serge Gaspers Mar 21 '11 at 10:34
• An interesting problem, but it's not totally clear what do you mean by "compact". Could you give a definition, please? – Tatiana Starikovskaya Mar 21 '11 at 11:30
• One possible definition for compact consistent with the picture is that it fits in a rectangle of small area. Is this correct? – Peter Shor Mar 21 '11 at 11:35
• Do you know if the problem becomes easy if the dependency is always L or always R ? – Gaurav Kanade Mar 21 '11 at 15:29
• Maybe I'm missing something, but it appears that you can always stack up or down in a straight line (since dependencies don't require touching). In this case the total area is exactly the number of cells, which is a lower bound and is thus optimal. – Suresh Venkat Mar 21 '11 at 19:12