Map segmentation

From Wikipedia, the free encyclopedia

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:^[1]

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.^[2]

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}\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 {R} ^{2}$ ;
The parameters P are the two sets of points;
The goal function G is

G(X_{1},\dots ,X_{n}):=\max _{i\in \{1,\dots ,n\}}\left(\left||P_{b}\cap X_{i}|-{\frac {|P_{b}|}{n}}\right|+\left||P_{r}\cap X_{i}|-{\frac {|P_{r}|}{n}}\right|\right).

It equals 0 if each region has exactly a fraction

1/n

of the points of each color.

Related problems

References

Related Articles

Wikiwand AI