What is the algorithm for building a slicing Tree?

Question

A problem on optimization where I need to build all slicing tree for a floorplan. My main issue is that I was not instructed how such floorplan is even created in the first place.

Thanks for your help.

Answer 1

http://cas.ee.ic.ac.uk/people/gac1/Synthesis/Lecture16.pdf

Provided all I needed to understand the problem.

From a starting set of rectangle create a random floorplan. Essentially your slice tree or the polish expression with random operators (V for vertical cut, H for horizontal cut) with your rectangles (denoted by a letter). Number of internal nodes being L-1 where L is the number of external leaves.

Let's say this polish expression: 712H3H645HVHV

To optimize the floorplan try to improve it from allowed moves:

• Swap two adjacent operands (leaf nodes) in the Polish expression.

• Take a chain of consecutive operators, e.g. “HVHV”, and complement it, e.g. “VHVH”.

• Swap an adjacent operator and operand. (But make sure still a skewed tree!)

To know if the solution have improved, you need to compute the area:

• Height( XYH ) = max( Height( X ), Height( Y ) )
• Width( XYH ) = Width( X ) + Width( Y )
• Height( XYV ) = Height( X ) + Height( Y )
• Width( XYV ) = max( Width( X ), Width( Y ) )