6
$\begingroup$

enter image description here

I want to generate random rectangular partition of a given $m*n$ rectangle under the constraint that it must be nowhere-neat partition. Nowhere-neat partition means that a dissection of a rectangle into smaller rectangles such that the original rectangle is not divided into two subrectangles.

My interest is in generating rectangular partitions that satisfy these two conditions: 1- No two adjacent rectangles share a common side (i.e. the union of two adjacent rectangles is not a rectangle). 2- At most two corners meet at a point.

Similar partitions appear under other names that include rectangulations, Tatami tilings, and non-slicing floorplans.

What algorithms are there that generate random fault-free rectangular partitions?

Update: Here is an example of random Mondrian rectangular partitions. Here the original rectangle is divided into two subrectangles. However, it is the opposite of what I want.

enter image description here

I do not require uniform distribution. I do not require a specific number of tiles, I only require that the number of tiles $T$ is within some fixed ratio $\epsilon \lt 1$ of $mn$ where $m= \theta(n)$ ($T=\epsilon*m*n$).

Improve this question
$\endgroup$
16
  • $\begingroup$ Could it be as simple as choosing some points at random, drawing horizontal and vertical lines through each, then repeatedly choosing at random any point still incident on "rays" in all 4 cardinal directions, choosing a random direction to "clear", and deleting the ray that lies in that direction? $\endgroup$ – j_random_hacker Apr 9 '19 at 18:27
  • 1
    $\begingroup$ What do you mean by "random distribution"? A process that always generates the number 5 is still considered a random process. A random variable that always has the value 5 is still a random variable, and is still considered random. So, I suspect asking for a random partition isn't capturing what you really want; I suspect you need to tell us something more about what properties you want the distribution to have. Otherwise, a deterministic algorithm that always output the same tiling would meet all stated requirements. Please edit the question to clarify all of these points in the question. $\endgroup$ – D.W.♦ Apr 9 '19 at 21:33
  • $\begingroup$ @MohammadAl-Turkistany D.W and you might have different views/feelings towards randomness, one of the most elusive concept in math, physics, etc. Let me continue with the simple academic intention of D.W as well as the question asked by j_random_hacker. Your question is not well-defined enough in the sense that the desired probability distribution of the output is not specified. For example, j_random_hacker has specified a naive algorithm. Do you consider that algorithm a valid solution, in term of randomness? $\endgroup$ – John L. Apr 11 '19 at 0:50
  • $\begingroup$ @MohammadAl-Turkistany in fact, I believe the essence of this question is how to define a probability distribution of the output given $m$ and $n$ (and a few other parameters) that can be considered random intuitively or suitably for your usage. It is quite possible that if that probability distribution is defined clearly, it might be trivial to come up with an algorithm. $\endgroup$ – John L. Apr 11 '19 at 0:57
  • $\begingroup$ @Apass.Jack Thanks for your comments. I accept j_random_hacker algorithm as long as it is clear enough to be implemented in a programming language (such as Python or Scratch). For instance here is an algorithm that generates random Mondrian rectangular partitions (it is opposite to what I want): scratch.mit.edu/projects/115945709 $\endgroup$ – Mohammad Al-Turkistany Apr 11 '19 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.