Map segmentation: Difference between revisions

Revision as of 07:58, 6 January 2016

Latest revision as of 06:15, 7 April 2025

(10 intermediate revisions by 5 users not shown)

Line 1:

TheIn [[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:<ref name=rag14>{{cite book | url=http://search.proquest.com/docview/1614472017 | 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, likeas 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]].<ref>{{Cite journal|doi=10.2307/147876|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>

‎ThereThere 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 |\frac{|P_b\cap X_i| - |P_b|} n \right| + \left| \frac{|P_r\cap X_i| - |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 ==

Line 27 ⟶ 40:

[[Category:Fair division]]

[[Category:Mathematical optimization]]