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.