CODEWITHSUNDEEP
algorithmtreeslice
Tristan
Tristan

Reputation: 1378

What is the algorithm for building a slicing Tree?

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.

Upvotes: 2

Views: 2769

Answers (1)

Tristan
Tristan

Reputation: 1378

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 ) )

Upvotes: 2

Related Questions