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

<p>I would like to place the squares  in some structure according to set of rules:</p>

<p>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.</p>

<p>If the dependency  is L and a new square i depends on j it can be placed:
<img src="https://i.sstatic.net/qVsqg.jpg" alt="enter image description here"></p>

<p>If the dependency  is R and a new square i depends on j it can be placed:
<img src="https://i.sstatic.net/id86u.jpg" alt="enter image description here">
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.</p>

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

<p><strong>The placement goal is to generate as compact a "mesh" as possible.</strong></p>

<p>For example if squares arrive in the format: new_square, dependent_on_square, dependency_flag</p>

<p>And we have </p>

<p>1, NULL, NULL</p>

<p>2, 1, R</p>

<p>3, 2, R</p>

<p>4, 2, L</p>

<p>5, 4, L</p>

<p>6, 5, L</p>

<p>7, 6, L</p>

<p>8, 7, L</p>

<p>9, 8, L</p>

<p>It is possible to create two arrangement 1) compact  2) not compact</p>

<p><img src="https://i.sstatic.net/SJ6FL.jpg" alt="enter image description here"></p>

<p>Definition for compact layout(placement):</p>

<p>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.</p>

<p>Note : The rectangular obtained as a result of padding shoud be as small as possible.</p>

<p>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) .</p>

<p>Demonstartion in the above examples
<img src="https://i.sstatic.net/CCAHX.jpg" alt="enter image description here"></p>

<p><strong>Could someone propose an algorithm to do such kind of placement?</strong></p>

CC BY-SA 2.5
2011-03-21T10:34:19.507Z
@Yakov: The question is missing.
Serge Gaspers
CC BY-SA 2.5
2011-03-21T11:30:34.650Z
An interesting problem, but it's not totally clear what do you mean by "compact". Could you give a definition, please?
Tatiana Starikovskaya
CC BY-SA 2.5
2011-03-21T11:35:11.793Z
One possible definition for compact consistent with the picture is that it fits in a rectangle of small area. Is this correct?
Peter Shor 
CC BY-SA 2.5
2011-03-21T12:16:21.707Z
I have added a definition
YAKOVM
CC BY-SA 2.5
2011-03-21T15:29:54.243Z
Do you know if the problem becomes easy if the dependency is always L or always R ?
Gaurav Kanade
CC BY-SA 2.5
2011-03-21T19:12:03.913Z
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
CC BY-SA 2.5
2011-03-21T19:42:44.697Z
I have clarified a placement preference.The preferable preferance is 1 and only then 2/3. Thank your for your note
YAKOVM
CC BY-SA 2.5
2011-03-22T18:21:19.663Z
Your example layouts violate your preference rule in several places.  For example, in both layouts, block 7 can be placed directly left of block 6, but it isn't.
Jeffε
CC BY-SA 2.5
2011-03-23T00:04:40.383Z
The original poster can clarify, but if we define "compact" as minimal with regards to length + height of the rectangle, then that would favor squares over rectangles...
sclv
<ds.algorithms><graph-theory><puzzles>
constraints placement question
YAKOVM
# constraints placement question

(Asked by: username_0 on 2011-03-21)

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:
![enter image description here](https://i.sstatic.net/qVsqg.jpg)

If the dependency is R and a new square i depends on j it can be placed:
![enter image description here](https://i.sstatic.net/id86u.jpg)
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

![enter image description here](https://i.sstatic.net/SJ6FL.jpg)

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
![enter image description here](https://i.sstatic.net/CCAHX.jpg)

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

**Tags:** ds.algorithms, graph-theory, puzzles
> **Comments:**
> **username_1**: @Yakov: The question is missing.  
> **username_2**: An interesting problem, but it's not totally clear what do you mean by "compact". Could you give a definition, please?  
> **username_3**: One possible definition for compact consistent with the picture is that it fits in a rectangle of small area. Is this correct?  
> **username_0**: I have added a definition  
> **username_4**: Do you know if the problem becomes easy if the dependency is always L or always R ?  
> **username_5**: 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.  
> **username_0**: I have clarified a placement preference.The preferable preferance is 1 and only then 2/3. Thank your for your note  
> **username_6**: Your example layouts violate your preference rule in several places.  For example, in both layouts, block 7 can be placed directly left of block 6, but it isn't.  
> **username_7**: The original poster can clarify, but if we define "compact" as minimal with regards to length + height of the rectangle, then that would favor squares over rectangles...  

---

## 0 answers

