mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, the map segmentation problem is a kind of

optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...

. 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 Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...

. * 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 Ancient Greece ( el, Ἑλλάς, Hellás) was a northeastern Mediterranean civilization, existing from the Greek Dark Ages of the 12th–9th centuries BC to the end of classical antiquity ( AD 600), that comprised a loose collection of cult ...

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\cdots\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,\dots,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 In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex r ...

or a

connected set In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint non-empty open subsets. Connectedness is one of the principal topological properties that ...

or at least a

measurable set In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simila ...

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

\mathbb^2

; * The parameters ''P'' are the two sets of points; * The goal function ''G'' is ::

G(X_1,\dots,X_n) := \max_ \left( \left , \frac n \ + \left,  \frac n\ \right).

: It equals 0 if each region has exactly a fraction

1/n

of the points of each color.

References

{{reflist Fair division Mathematical optimization

Notation

Examples

Related problems

References