|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A study on the number of Hierarchical Rectangular Partitions of Order k | | Shankar Balachandran
; Sajin Koroth
; | | Date: |
6 Dec 2011 | | Abstract: | 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<k$. | | Source: | arXiv, 1112.1374 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER