Map segmentation

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: :<math>C = X_1\sqcup\cdots\sqcup X_n</math>

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: :<math>\arg\min_X G(X_1,\dots,X_n \mid P)</math> 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 <math>P_b</math> of blue points and a set <math>P_r</math> of red points. Divide the plane into <math>n</math> regions such that each region contains approximately a fraction <math>1/n</math> of the blue points and <math>1/n</math> of the red points. Here: The cake C* is the entire plane <math>\mathbb{R}^2</math>; The parameters P* are the two sets of points; The goal function G* is :: <math>G(X_1,\dots,X_n) := \max_{i\in \{1,\dots, n\}} \left( \left ||P_b\cap X_i| - \frac n \right| + \left| |P_r\cap X_i| - \frac{ |P_r|} n\right| \right).</math> : It equals 0 if each region has exactly a fraction <math>1/n</math> 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.

References