Suppose an area is divided into N irregular regions. Unless N is very small there will be many ways in which a new division of the area can be obtained by merging adjacent regions. I want to identify these for a case in which N = 17.

More formally, define a derived region as being: a) any of the original regions, or b) any region formed by merging adjacent derived regions. Note that (b) can be applied recursively. Suppose for example that A, B and C are original regions with A adjacent to B and B to C, but not A to C. Then A+B is a derived region and is adjacent to C (since B is adjacent to C), so that A+B+C is also a derived region. Thus a derived region contains at least 1 and at most N of the original regions.

Question: Given an integer M (1 < M < N), what is the most efficient method of identifying all possible divisions of the whole area into M derived regions?

What I have done: I searched in Google but nothing seemed helpful (there is a region-merging algorithm used in segmentation of colour images but this does not look relevant). A method that occurs to me is this:

a) First find all possible divisions for M = N-1. This involves just one merger of adjacent regions, so the number of possibilities will not be too large (in my case 38).

b) For each division from (a), find all possible divisions for M = N-2. Eliminate any duplicates.

c) And so on for M = N-3, etc.

This should work, but is likely to generate a lot of duplicates, so perhaps there is a better method.

Update 13 Dec 2013 A possible approach is as follows:

1) Represent each original zone by a distinct prime integer, and let A be the product of all the primes used.

2) Represent each derived zone by the product of the primes representing its member zones. The use of primes ensures that two derived zones are non-overlapping if the highest common factor of the products representing them is one.

3) Each division of the area into M derived zones then corresponds to a unique factorisation of A, subject to the condition that each factor represent a derived zone.

Of course this does not solve the problem, since it still requires a method for identifying the relevant factorisations. It does however convert the spatial problem into a number-theoretic problem which may be easier to solve.


How about this:

1) Find any one possible division of $M$ derived regions that covers all $N$ original regions. We'll use this as a start division.

2) Since $M < N$, at least 1 derived region $r$ has $N_r>1$ original regions (called members for ease of description). So we pick $r$ and check its $N_r$ members one by one. For each member in $r$, if we can move it to a neighboring derived region, we get a new division. Eliminate duplicates.

3) Redo (2) for anther $r$ that has $N_r>1$, until we cannot find a new division.

4) Count the number of divisions we have found.

Some divisions may need more than 1 move from the starting division. I'll explain why this algorithm can get them.

Let division $D_0$ represent the starting division, and set $\mathbb{D}_k$ represent the set of divisions that need minimum $k$ moves from $D_0$. When running Step 2 on $D_0$, we will get all divisions in $\mathbb{D}_1$. When running Step 2 on all divisions in $\mathbb{D}_1$, after eliminating duplicates, we'll get $\mathbb{D}_2$, and so on. So eventually we will get all available $\mathbb{D}_k, k\in\{1,2,...\}$.

  • $\begingroup$ Thank you, an interesting suggestion. At step 3, presumably $r$ would be chosen from those derived regions that had not already been obtained by moving an original region at step 2? $\endgroup$ – Adam Bailey Oct 23 '13 at 6:50
  • $\begingroup$ Please ignore the last sentence of my earlier comment which is confused (wasn't quick enough to edit it). A further thought: will this method identify all possible divisions? Some divisions will need more than one move from the starting division and I can't see that the method as stated allows for that. $\endgroup$ – Adam Bailey Oct 23 '13 at 7:17
  • $\begingroup$ @Adam Good question. Step 2 will be applied to all existing divisions we have found so far. One way to handle this is to build a queue for existing divisions. Apply Step 2 on all possible region $r$ in the division at the head of queue. After it's done, remove this division from the queue. When a new division is found, we put it in the queue. In terms of divisions that need more than one move from the starting division, I edited my post for more explanation. $\endgroup$ – Shushan Wen Oct 23 '13 at 16:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.