• Images
• Videos
• Documents
• Books
• Articles

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 ⊔ ⋯ ⊔ X n {\displaystyle 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 , … , X n ∣ P ) {\displaystyle \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 {\displaystyle P_{b}} of blue points and a set P r {\displaystyle P_{r}} of red points. Divide the plane into n {\displaystyle n} regions such that each region contains approximately a fraction 1 / n {\displaystyle 1/n} of the blue points and 1 / n {\displaystyle 1/n} of the red points. Here:

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

G ( X 1 , … , X n ) := max i ∈ { 1 , … , n } ( | | P b ∩ X i | − | P b | n | + | | P r ∩ X i | − | P r | n | ) . {\displaystyle G(X_{1},\dots ,X_{n}):=\max _{i\in \{1,\dots ,n\}}\left(\left|{\frac {|P_{b}\cap X_{i}|-|P_{b}|}{n}}\right|+\left|{\frac {|P_{r}\cap X_{i}|-|P_{r}|}{n}}\right|\right).} It equals 0 if each region has exactly a fraction 1 / n {\displaystyle 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.

References

1. Raghuveer Devulapalli (2014). Geometric Partitioning Algorithms for Fair Division of Geographic Resources. Advisor: John Gunnar Carlsson. A Ph.D. thesis submitted to the faculty of university of Minnesota. ProQuest 1614472017. /wiki/ProQuest ↩

2. Boyd, Thomas D.; Jameson, Michael H. (1981). "Urban and Rural Land Division in Ancient Greece". Hesperia. 50 (4): 327. doi:10.2307/147876. JSTOR 147876. /wiki/Doi_(identifier) ↩