Map segmentation: Difference between revisions

Revision as of 08:19, 6 January 2016

Revision as of 16:34, 6 January 2016

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 (Advisor: John Gunnar Carlsson) | year=2014}}</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.

Line 8:

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

Line 21:

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 ==