Map segmentation

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\backslash sqcup\backslash cdots\backslash 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:

:$\backslash arg\backslash min\_X\; G(X\_1,\backslash dots,X\_n\; \backslash 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.

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

:: $G(X\_1,\backslash dots,X\_n)\; :=\; \backslash max\_\{i\backslash in\; \backslash \{1,\backslash dots,\; n\backslash \}\}\; \backslash left(\; \backslash left\; |\backslash frac$

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

• 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.

{{reflist}}

Category:Fair division

Category:Mathematical optimization