Сегментация карты

В математике является проблема сегментации карты разновидностью задачи оптимизации . Он включает в себя определенный географический регион, который необходимо разделить на более мелкие субрегионы для достижения определенной цели. Типичные цели оптимизации включают в себя:

• Минимизация загруженности автопарка, закрепленного за субрегионами;
• Балансировка потребления ресурса, как в случае с честным разрезанием торта .
• Определение оптимального расположения складов снабжения;
• Максимизация охвата наблюдения.

Справедливое разделение земли было важным вопросом с древних времен, например, в Древней Греции .

Обозначения

Существует географический регион, обозначенный буквой C («торт»).

Раздел C, обозначаемый X, представляет собой список непересекающихся подобластей, объединением которых является C:

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

Существует определенный набор дополнительных параметров (таких как: препятствия, неподвижные точки или функции плотности вероятности), обозначаемых P.

На множестве всех разделов существует вещественная функция, обозначаемая G («цель»).

Задача сегментации карты состоит в том, чтобы найти:

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

где минимизация осуществляется на множестве всех разбиений C.

Часто существуют ограничения геометрической формы разделов, например, может потребоваться, чтобы каждая часть была выпуклым множеством , или связным множеством , или, по крайней мере, измеримым множеством .

Примеры

1. Красно-синяя перегородка : есть комплект $P_{b}$ синих точек и набора $P_{r}$ красных точек. Разделите самолет на $n$ такие регионы, что каждый регион содержит примерно долю $1/n$ синих точек и $1/n$ из красных точек. Здесь:

• Торт С — это вся плоскость $\mathbb {R} ^{2}$;
• Параметры P — это два набора точек;
• Целевая функция G равна

$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).$

Он равен 0, если каждый регион имеет ровно дробь $1/n$ точек каждого цвета.

Связанные проблемы

• Диаграмма Вороного — это особый тип задачи сегментации карты.
• Честная разрезка торта , когда торт двумерный, является еще одной специфической проблемой сегментации карты, когда торт двумерный, как в задаче о разделе земли Хилла-Бека .
• Теорема Стоуна-Тьюки связана с конкретной проблемой сегментации карт.