Map segmentation
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:
- [math]\displaystyle{ C = X_1\sqcup\cdots\sqcup X_n }[/math]
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:
- [math]\displaystyle{ \arg\min_X G(X_1,\dots,X_n \mid P) }[/math]
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 [math]\displaystyle{ P_b }[/math] of blue points and a set [math]\displaystyle{ P_r }[/math] of red points. Divide the plane into [math]\displaystyle{ n }[/math] regions such that each region contains approximately a fraction [math]\displaystyle{ 1/n }[/math] of the blue points and [math]\displaystyle{ 1/n }[/math] of the red points. Here:
- The cake C is the entire plane [math]\displaystyle{ \mathbb{R}^2 }[/math];
- The parameters P are the two sets of points;
- The goal function G is
- [math]\displaystyle{ G(X_1,\dots,X_n) := \max_{i\in \{1,\dots, n\}} \left( \left |\frac{|P_b\cap X_i| - |P_b|} n \right| + \left| \frac{|P_r\cap X_i| - |P_r|} n\right| \right). }[/math]
- It equals 0 if each region has exactly a fraction [math]\displaystyle{ 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
- ↑ Raghuveer Devulapalli (Advisor: John Gunnar Carlsson) (2014). Geometric Partitioning Algorithms for Fair Division of Geographic Resources. A Ph.D. thesis submitted to the faculty of university of Minnesota. ProQuest 1614472017.
- ↑ Boyd, Thomas D.; Jameson, Michael H. (1981). "Urban and Rural Land Division in Ancient Greece". Hesperia 50 (4): 327. doi:10.2307/147876.
![]() | Original source: https://en.wikipedia.org/wiki/Map segmentation.
Read more |