A study on the number of Hierarchical Rectangular Partitions of Order k

Details A study on the number of Hierarchical Rectangular Partitions of Order k A study on the number of Hierarchical Rectangular Partitions of Order k

2011-12-06

arxiv.org/abs/1112.1374v1

Computer Science

Discrete Mathematics

Submitted to electronic journal of integer sequences for review

Scientific paper

Given a rectangle $R$, a Rectangular Dissection (RD) is a subdivision of $R$ into smaller rectangles by non-intersecting vertical or horizontal segments. Rectangular dissections are also called floorplans. In this paper we study the number of rectangular dissections which can be decomposed hierarchically. A rectangular partition is said to be a Hierarchical Rectangular Dissection (HRD) of order $k$ if the rectangular dissection can be obtained by starting from a single rectangle by embedding rectangular dissections of at most $k$ basic rectangles hierarchically. When $k=2$ this is exactly the class of guillotine rectangular dissections. Ackerman et al. proved that point-free rectangular dissections are in bijective correspondence with Baxter permutations. We characterize HRD-$k$, a sub-class of point-free rectangular dissections, based on the Baxter permutations corresponding to them. We provide a recurrence relation for the distinct number of HRD-$k$ with $n$ rooms by proving that they are in bijective correspondence with a family of rooted trees called generating trees of order $k$. Based on this recurrence relation we give a polynomial time algorithm for generating the number of such distinct rectangular dissections. This gives rise to family of integer sequences $\mathbb{I}=\{I_k\}$ where $I_{k,i}$ correspond to the number different $\HRD_k$ with $i$ rooms. Based on the characterization of permutations corresponding to HRD's of order $k$ we prove that there are at least $3^{n-k}$ which are in-decomposable, that is it is not $\HRD_k$ for any $j

Affiliated with

Also associated with

No associations

Rating

A study on the number of Hierarchical Rectangular Partitions of Order k does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A study on the number of Hierarchical Rectangular Partitions of Order k, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A study on the number of Hierarchical Rectangular Partitions of Order k will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-381887