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