Transformation between space partitions

Question

We have a space S, being partitioned into a set of polygons P containing $n$ polygons $P_1, P_2,..., P_n$. Given $n$ constants $k_1,k_2,...,k_n $. Apply a transformation $T$ from partition $P$ to space partition $Q$(of polygons) such that,

$$ \textrm{area}(Q_i) = k_i \: \forall i \in [1,n] $$ $$ Q\ \textrm{is a partition of}\ S $$

$$ P_i \in \textrm{adj}(P_j) \implies Q_i \in \textrm{adj}(Q_j) $$ given that $$ \textrm{area}(S) = \sum_i k_i $$

How to algebraically formulate $T$? Is there any exact/approximate solution for such a problem?

Edit:(context)

I am working with village maps(space partition $P$) that are not legal but roughly correct. Every land owner is entitled to a certain area($k$'s) which is legal. We need to transform $P$ to $Q$ such that the total area is preserved and individual areas match legal data.

Answer 1

I thought at first that this issue could be amenable to Lloyd's algorithm. But it is not the case.

I have had a basic idea that, hopefuly mixed with others, could realize the overall transformation.

Without loss of generality, we can assume that all areas are reduced to percentages (i.e., sum of all areas = 1).

The idea is to manage groups of 3 regions having a common point $P$ as represented here [don't pay attention to the 3D aspect : it was easier for me to do it that way]

Consider a "group of 3 regions"

• if the sum $s=h_1+h_2+h_3$ of initial areas is approximately equal to the sum of final areas $t=k_1+k_2+k_3$ (Indeed, in this case where $s \approx t$, any "inside" change doesn't affect the rest of the cells) : move point $P$ into position $P'$ still in the union of three cells, so as to meet the requirement for the new areas are

$$h_1 \to k_1,h_2 \to k_2,h_3 \to k_3 \tag{1}$$

[Technicaly, one must fulfill :

$$h_1-k_1=\underbrace{\det(\vec{P'A},\vec{P'B})}_{\text{oriented-area(P'AB)}}-\underbrace{\det(\vec{PA},\vec{PB})}_{\text{oriented-area(PAB)}},$$

with similar operations for the other area differences.]

If no point $P$ meets this requirement (1), for example due to concavities of some regions, it is possible to introduce a new vertex on an edge £PA,PB,PC$ issued from $P$ in order to improve flexibility.

• If, on the contrary, the group of 3 regions has its $s$ very different from its $t$, another general idea would be to "inflate or deflate" its cells by borrowing/giving them part of their territory in order to get a $t$ value closer to the $s$ value while preserving the adjacencies. [It remains to convert this general idea into an operational one...].

Will this, used iteratively, give rise to a converging process (like in Lloyd's algorithm) ? Or only an improvement narrowing the gap ? I have honestly no idea. But it's worth attempting it...

Answer 2

First, a remark: in some cases, it is necessary to create new edges or delete existing edges.

Otherwise take a square village, an odd number $n$ of $P_i$, all in a triangle shape, and targets are $Q_i$ all of equal size. If $Q_i$ stay triangles, the problem is odd equidissection of a square, which is infeasible (Monsky's theorem).
Note that there is a lower bound to the difference of areas, which is not zero - although it may be sufficiently small for practical applications, of course.

---

Then, not a full solution but a sketch for the case where area modifications are small enough. This assumes a convex village, hence all polygons form a connected graph.

The idea is to slide each edge orthogonally, with a distance small enough that the edge does not make a neighbour edge disappear. (For all edges between polygons, not for the village external edges).
Then, areas of the two polygons on each side of the edge are modified by the same quantity, which is added to one polygon and subtracted from the other one. This area is, on first order approximation, the product of the edge length by the gliding distance.
Whatever the modifications we want to make, there is always a solution: this is equivalent to the problem of getting a given distribution of charges on vertices of a connected graph, with a null sum, from a state where all vertices charges are null, by transporting them along the edges. (I have a reference to that, but it is in a book and in French).

So the plan is to solve a linear system to get the gliding distance of each edge.

For $n$ polygons, there are at least $n-1$ edges, in which case the system has rank $n-1$ (due to the fact that the sum of all modifications equals zero, so there are $n-1$ equations and $n-1$ variables) and solution is unique.
If there are more than $n-1$ edges - by far the most frequent case, unless land owners have divided the village into stripes :-) - then the solution is not unique, and some heuristics could be added to select a solution that gives better convergence, or has less risk of deleting an edge in later iterations.
I have no specific heuristics in mind so far, and anyway it would depend upon the method used to solve the system.
As this is a solution to the linearized problem where we do not take into account edges length modification when gliding, the solution is not exact, so the process has to be iterated. So far I have no proof that it converges, although it seems intuitive that it should, for small enough modifications.

---

Note that this solution has the advantage of letting each land owner stay on its land, for small modifications.
If this is not a requirement, then a variant would be to try having edges orthogonal one to each other: then gliding would not change their length, and solving the linear system would be exact on first iteration.

I have no idea so far as how to get this initial position with all edges orthogonal to each other, although if we are allowed to completely change the partition, there is surely a way to be found...