Suvarna Garge (Editor)

Map segmentation

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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:

Contents

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

    C = X 1 ⊔ ⋯ ⊔ 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 ∣ 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
    • It equals 0 if each region has exactly a fraction 1 / n of the points of each color.
  • 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

    Map segmentation Wikipedia
    (Text) CC BY-SA