Map segmentation

In mathematics, 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, as 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\bigsqcup \cdots \bigsqcup 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 \underset{X}{\min }G(X_1,\dots ,X_n\mid P)$

where the minimization is on the set of all partitions of C. Often, there are geometric shape constraints on the partitions, e.g., it may be required that each part be a convex set or a connected set or at least a measurable set.

Examples

1. Red-blue partitioning: there is a set $P_b$ of blue points and a set $P_r$ of red points. Divide the plane into $n$ regions such that each region contains approximately a fraction $1/n$ of the blue points and $1/n$ of the red points. Here:

• The cake C is the entire plane ${\mathbb{ℝ}}^2$;
• The parameters P are the two sets of points;
• The goal function G is

$G(X_1,\dots ,X_n):=\underset{i\in \{1,\dots ,n\}}{\max }(\left|\frac{|P_b\cap X_i|-|P_b|}{n}\right|+\left|\frac{|P_r\cap X_i|-|P_r|}{n}\right|).$

It equals 0 if each region has exactly a fraction $1/n$ of the points of each color.

Related problems

• A Voronoi diagram is a specific type of map-segmentation problem.
• Fair cake-cutting, when the cake is two-dimensional, is another specific map-segmentation problem when the cake is two-dimensional, like in the Hill–Beck land division problem.
• The Stone–Tukey theorem is related to a specific map-segmentation problem.