Segmentación de mapas

En matemáticas , el problema de segmentación de mapas es un tipo de problema de optimización . Implica una determinada región geográfica que debe dividirse en subregiones más pequeñas para lograr un objetivo determinado. Los objetivos de optimización típicos incluyen: ^[1]

• Minimizar la carga de trabajo de una flota de vehículos asignados a las subregiones;
• Equilibrar el consumo de un recurso, como en un reparto justo del pastel .
• Determinar las ubicaciones óptimas de los depósitos de suministros;
• Maximizar la cobertura de vigilancia.

La división justa de la tierra ha sido una cuestión importante desde la antigüedad, por ejemplo en la antigua Grecia . ^[2]

Hay una región geográfica denotada por C ("pastel").

Una partición de C, denotada por X, es una lista de subregiones disjuntas cuya unión es C:

${\displaystyle C=X_{1}\sqcup\cdots\sqcup X_{n}}$

Hay un cierto conjunto de parámetros adicionales (como: obstáculos, puntos fijos o funciones de densidad de probabilidad), denotados por P.

Hay una función de valor real denotada por G ("objetivo") en el conjunto de todas las particiones.

El problema de segmentación del mapa consiste en encontrar:

${\displaystyle \arg \min _{X}G(X_{1},\puntos ,X_{n}\mid P)}$

donde la minimización está en el conjunto de todas las particiones de C.

A menudo, existen restricciones de forma geométrica en las particiones, por ejemplo, puede requerirse que cada parte sea un conjunto convexo o un conjunto conexo o al menos un conjunto medible .

1. Partición rojo-azul : hay un conjunto de puntos azules y un conjunto de puntos rojos. Divida el plano en regiones de modo que cada región contenga aproximadamente una fracción de los puntos azules y de los puntos rojos. Aquí: ${\displaystyle P_{b}}$$Estilo de visualización P_{r}$${\estilo de visualización n}$${\estilo de visualización 1/n}$${\estilo de visualización 1/n}$

• La tarta C es todo el plano ;${\displaystyle \mathbb {R} ^{2}}$
• Los parámetros P son los dos conjuntos de puntos;
• La función objetivo G es

${\displaystyle G(X_{1},\puntos ,X_{n}):=\max _{i\in \{1,\puntos ,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).}$

Es igual a 0 si cada región tiene exactamente una fracción de los puntos de cada color.${\estilo de visualización 1/n}$

• Un diagrama de Voronoi es un tipo específico de problema de segmentación de mapas.
• El corte justo de la torta , cuando la torta es bidimensional, es otro problema específico de segmentación de mapas cuando la torta es bidimensional, como en el problema de división de tierras de Hill-Beck .
• El teorema de Stone-Tukey está relacionado con un problema específico de segmentación de mapas.