Map segmentation: Difference between revisions

Revision as of 07:59, 6 January 2016

Revision as of 08:19, 6 January 2016

Line 22:

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 <math>P_b</math> of blue points and a set <math>P_r</math> of red points. Divide the plane into <math>n</math> regions such that each region contains approximately a fraction <math>1/n</math> of the blue points and <math>1/n</math> of the red points. Here:

* The cake C is the entire plane <math>\mathbb{R}^2</math>;

* The parameters P are the two sets of points;

* The goal function G is: <math>G(X_1,\dots,X_n) := max_{i\in 1\dots n} \left(||P_b\cap X_i| - |P_b|/n| + ||P_r\cap X_i| - |P_r|/n| \right)</math>. It equals 0 if each region has exactly a fraction <math>1/n</math> 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 ==