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

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

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

Справедливое разделение земли было важной проблемой с древних времен, например в древняя Греция.^[2]

Обозначение

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

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

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

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

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

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

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

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

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

Примеры

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

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

${\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).}$

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

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

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

Рекомендации

1. Рагхувир Девулапалли (советник: Джон Гуннар Карлссон) (2014). Алгоритмы геометрического разделения для справедливого разделения географических ресурсов. Доктор философии Диссертация подана на факультет Миннесотского университета. ProQuest  1614472017.
2. Бойд, Томас Д .; Джеймсон, Майкл Х. (1981). «Разделение городских и сельских земель в Древней Греции». Hesperia. 50 (4): 327. Дои:10.2307/147876. JSTOR  147876.