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]

• 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

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 = X _{1\sqcup … \sqcup} X _{n}

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:

\arg min _{X} G(X _{1,...,X} _{n} \mid P) 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

P _{b} of blue points and a set P _{r} 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:

• The cake C is the entire plane

R ^{2} ;

• The parameters P are the two sets of points;
• The goal function G is

G(X _{1,...,X} _{n)} : = max _{i\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

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

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