Jump to content

Map segmentation

From Wikipedia, the free encyclopedia

In 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:[1]

  • Minimizing the workload of a fleet of vehicles assigned to the sub-regions;
  • Balancing the consumption of a resource, as 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.[2]

Notation

[edit]

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:

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:

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

[edit]

1. Red-blue partitioning: there is a set of blue points and a set of red points. Divide the plane into regions such that each region contains approximately a fraction of the blue points and of the red points. Here:

  • The cake C is the entire plane ;
  • The parameters P are the two sets of points;
  • The goal function G is
It equals 0 if each region has exactly a fraction of the points of each color.
[edit]

References

[edit]
  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.
  2. ^ Boyd, Thomas D.; Jameson, Michael H. (1981). "Urban and Rural Land Division in Ancient Greece". Hesperia. 50 (4): 327. JSTOR 147876.