The Region Merging Algorithm

An alternative solution to the problem is to treat it as a set of potentially inconsistent constraints:

$$M_{AB} = \textrm{round}\left(\frac{- P_{AB}}{2 \pi N_{AB}}\right).$$ (7)

The problem is then one of finding the set of consistent constraints which lead to a low (ideally minimal) cost.

Let $K_{AB} = - P_{AB}/(2 \pi N_{AB})$.

Consider the difference in cost between $M_{AB} = L_{AB} = \textrm{round}(K_{AB})$ and $M_{AB} = L_{AB} \pm 1$. The cost difference is:

$$\Delta C_{AB} = 8\pi^2 N_{AB} \left( \frac{1}{2} \pm (K_{AB} - L_{AB}) \right)$$ (8)

Since, by definition of rounding, $-\frac{1}{2} \le K_{AB} - L_{AB} \le \frac{1}{2}$, then $\Delta C_{AB} \ge 0$ for both cases, confirming that $M_{AB} = L_{AB}$ is (locally) the best solution.

The smallest cost difference is:

$$\Delta C_{AB} = 8\pi^2 N_{AB} \left( \frac{1}{2} - \vert K_{AB} - L_{AB} \vert \right).$$ (9)

Choose the interface where this cost difference is the largest. That is, choose the pair of regions where getting the offset ``wrong'' is the most disastrous.

Therefore, select the pair of regions according to:

$$AB = \arg \max_{RS} \Delta C_{RS}.$$ (10)

Once this pair is selected, merge them into a new, single region $Q$ using the ``optimal'' offset $L_{AB}$. Update the statistics for all interfaces to this new region. That is, for all regions $W$, the new statistics are:

$$N_{QW} = N_{AW} + N_{BW}$$ (11)

$$P_{QW} = P_{AW} + P_{BW}$$ (12)

From these, calculate $K_{QW}$, $L_{QW}$ and then $\Delta C_{QW}$ and then repeat the selection process to choose a new pair of regions to merge.

Keep merging regions until there are no more interfaces between regions (usually when only one region remains if there is a single connected set of regions initially).

As each iteration of this algorithm merges two regions, the number of iterations required is $N-1$. Within each iteration a search for the maximum $\Delta C$ value must take place, followed by the updating or deletion of all constraints related to the two selected regions.