Partitions

Mariah A. Knowles

Wed, Jan 2, 2019

Muthukrishnan et al wrote a paper about a problem I've been thinking about lately.

Imagine a flat, rectangular 2d space, like a tabletop or the floor of a room. How many ways are there to cut this room up into rectangular regions? Well, there's an infinite number, if we say there can be really really really small regions each the area of a fraction of an inch. So let's say we can only cut the room up along the lines of some grid, each gridline spaced out half a foot or so. I can't see much need for smaller cuts than that.

I ask this because I wanted to randomly generate a board game. One possible game is the whole room is one big region. (Not a very interesting game, but possible and valid nonetheless.) Another possible game is where every box of the grid is its own region. (Again not interesting, but still valid.) Most random games should have some mix of big and small regions, all pieced together like some weird brick pattern.

(One attempt at making a program to generate these "partitionings" of the 2d space kept making something that looks like modern Army camo.)

If I can tell how many possible partitionings there are, then I can know how likely each one should be: one divided by the total possible number. This is important if I want my randomly generated board game to not have any particular bias about the placement of the regions.

There are a few different ways to go about cutting up a room. Muthukrishnan et al give three strategies: arbitrary, hierarchical, and pxp (read "p by p"). What I wanted is what they call an arbitrary strategy, the other two imposing biases towards some possible partitionings over others, or outright preventing whole types of patterns. Muthukrishnan et al argue that searching all possible arbitrary partitionings for one that optimizes for some requirement is NP-Hard, which tells us that there are a lot of possible combinations to dig through.

Conant and Michaels published a paper in Springer giving an equation for counting these partitionings, but only of a certain hierarchical form, not the arbitrary cases I was interested in, and only considering partitions of a square room, not of a room of any size.

So why is it hard to count these possibilities? Well, honestly I wish I knew how to put this into words, but I don't. But, I don't need to for what I originally wanted to do here.

Can I randomly generate a partitioning of a 2d space, without ever knowing how many possible partitionings there are to choose from?

That's what I've tried to do in this project here:

The colors are also randomly generated according to a palette I like, but they have no real meaning and are just to help tell regions apart. You can also click on the grid to generate a new one.

I believe that these generated results are without any bias towards one type of pattern over another. I'll start with an inductive proof, where we show where this is true for a very small case, then show it continues to be true as we "build up" to some bigger case we care about.

Assume we have a 1x1 space (just one corner of the room). There is only one possible partitioning of this space: the whole thing is one region. We'll call this region 1.

Next, for a 2x1 space, there are two options: all region 1, or one pixel is region 1 and the other is region 2. Since there are only two possibilities, a 50/50 coin flip would choose between them without any bias.

And so on, for an nx1 space, we can first create an unbiased (n-1)x1 space, and "grow" this by either adding another pixel for the right-most region, or by starting a new region incrementally. Those are the only two options, so a 50/50 coin flip continues to prevent bias. And, all regions must be rectangular, since with only one row to work with, no other shapes are possible. (We don't want to accidentally create a non-rectangular shape at any point.)

Once we have an nx1 space (going left/right), we can think about growing along the other direction (up/down). For the left-most region of the second row, we have only two options: either grow the region above us down one row, or start a new region. This gives us an L-shaped space, and if we choose 50/50 here again, we still have no bias.

Now, extending this L-shaped space into an nx2 space (growing the rest of the second row), we can keep going in the same manner. However, there are a three cases we might run into along the way:

• If we are underneath a region we have previously decided not to grow down, we cannot grow it down now, else that would result in a non-rectangular shape. So, the options are to either (i) grow the region on the left to the right (which we know cannot be the same region as above, due to assuming what we have so far is valid and rectangular), or (ii) start a new region. In this case we do a 50/50 flip to prevent bias.
• If we just completed growing a region down, we cannot grow that region also to the right, else that would break the rectangular requirement. In this case, our options are to either (i) grow the region now above us down as well or (ii) start a new region. Again, 50/50.
• Otherwise, we can do either of the three options to (i) grow the region above us down for however many pixels wide it is, (ii) grow the region on the left to the right one pixel, or (iii) start a new region. Here we have to randomly choose between three options with a "three-sided coin" so to say, or a 6-sided die that we color-code so there are only three possible results.

Once we have completed the L-shape into an nx2 space, we can just keep continuing in this way, adding one row at a time, until we have the full nxm space to fill our room, without any bias and with only rectangular regions.

So even though I have no idea how many possible partitionings there are, I can at least sample from those possibilities one at a time.