Map segmentation

The map segmentation problem is a kind of optimization problem. It involves a certain geographic region that has to be partitioned into smaller sub-regions in order to achieve a certain goal. Typical optimization objectives include:

• Minimizing the workload of a fleet of vehicles assigned to the sub-regions;
• Balancing the consumption of a resource, like in fair cake-cutting.
• Determining the optimal locations of supply depots;
• Maximizing the surveillance coverage.

Fair division of land has been an important issue since ancient times, e.g. in ancient Greece.

Notation

There is a geographic region denoted by C ("cake").

A partition of C, denoted by X, is a list of disjoint subregions whose union is C:

$C=X_{1}\sqcup \cdots \sqcup X_{n}$

‎There is a certain set of additional parameters (such as: obstacles, fixed points or probability density functions), denoted by P.

There is a real-valued function denoted by G ("goal") on the set of all partitions.

The map segmentation problem is to find:

$\arg \min _{X}G(X_{1},\dots ,X_{n}|P)$

where the minimization is on the set of all partitions of C.