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]

Notación

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},\dots ,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 .

Ejemplos

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}}$ ${\displaystyle P_{r}}$ ${\displaystyle n}$ ${\displaystyle 1/n}$ ${\displaystyle 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},\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).}$

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

Problemas relacionados

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

Referencias

1. Raghuveer Devulapalli (2014). Algoritmos de partición geométrica para la división justa de recursos geográficos . Asesor: John Gunnar Carlsson. Tesis de doctorado presentada ante la facultad de la Universidad de Minnesota. ProQuest  1614472017.
2. Boyd, Thomas D.; Jameson, Michael H. (1981). "División de tierras urbanas y rurales en la antigua Grecia". Hesperia . 50 (4): 327. JSTOR  147876.