Map segmentation explained

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]

Fair division of land has been an important issue since ancient times, e.g. in ancient Greece.[2]

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=X1\sqcup\sqcupXn

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:

\argminXG(X1,...,Xn\midP)

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

Pb

of blue points and a set

Pr

of red points. Divide the plane into

n

regions such that each region contains approximately a fraction

1/n

of the blue points and

1/n

of the red points. Here:

R2

;

G(X1,...,Xn):=maxi\in

} \left(\left |\frac
- P_b
n \right| + \left| \frac
- P_r
n\right| \right).

It equals 0 if each region has exactly a fraction

1/n

of the points of each color.

Related problems

Notes and References

  1. Book: Geometric Partitioning Algorithms for Fair Division of Geographic Resources . A Ph.D. thesis submitted to the faculty of university of Minnesota . Raghuveer Devulapalli. Advisor: John Gunnar Carlsson . 2014. .
  2. 10.2307/147876. 147876. Urban and Rural Land Division in Ancient Greece. Hesperia. 50. 4. 327. 1981. Boyd. Thomas D.. Jameson. Michael H..