# Map segmentation

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Map_segmentation
> Markdown URL: https://mediated.wiki/source/Map_segmentation.md
> Source: https://en.wikipedia.org/wiki/Map_segmentation
> Source revision: 1333062363
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [mathematics](/source/mathematics), the '''map segmentation''' problem is a kind of [optimization problem](/source/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:<ref name=rag14>{{cite book | title=Geometric Partitioning Algorithms for Fair Division of Geographic Resources | publisher=A Ph.D. thesis submitted to the faculty of university of Minnesota | author=Raghuveer Devulapalli|others=Advisor: John Gunnar Carlsson | year=2014|id = {{ProQuest|1614472017}}}}</ref>
* Minimizing the workload of a fleet of vehicles assigned to the sub-regions;
* Balancing the consumption of a resource, as in [fair cake-cutting](/source/fair_cake-cutting).
* Determining the optimal locations of supply depots;
* Maximizing the surveillance coverage.

[Fair division](/source/Fair_division) of land has been an important issue since ancient times, e.g. in [ancient Greece](/source/ancient_Greece).<ref>{{Cite journal|jstor=147876|title=Urban and Rural Land Division in Ancient Greece|journal=Hesperia|volume=50|issue=4|pages=327|year=1981|last1=Boyd|first1=Thomas D.|last2=Jameson|first2=Michael H.}}</ref>

== 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](/source/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](/source/convex_set) or a [connected set](/source/connected_set) or at least a [measurable set](/source/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{|P_b|} 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](/source/Voronoi_diagram) is a specific type of map-segmentation problem.
* [Fair cake-cutting](/source/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](/source/Hill%E2%80%93Beck_land_division_problem).
* The [Stone–Tukey theorem](/source/Stone%E2%80%93Tukey_theorem) is related to a specific map-segmentation problem.

== References ==
{{reflist}}

Category:Fair division
Category:Mathematical optimization

---
Adapted from the Wikipedia article [Map segmentation](https://en.wikipedia.org/wiki/Map_segmentation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Map_segmentation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.