지도 분할

수학에서 지도 세분화 문제는 일종의 최적화 문제다.그것은 특정한 목표를 달성하기 위해 더 작은 하위 영역으로 분할되어야 하는 특정한 지리적 지역을 포함한다.대표적인 최적화 목표는 다음과 같다.^[1]

• 하위 지역에 배정된 차량 비행대의 작업량 최소화
• 공정한 케이크 커팅에서와 같이 자원의 소비 균형 조정.
• 공급 저장소의 최적 위치 결정
• 보안 감시 범위 극대화.

예를 들어 고대 그리스에서 땅의 공정한 분할은 고대부터 중요한 문제였다.^[2]

표기법

C("케이크")로 표시된 지리적 지역이 있다.

X가 나타내는 C의 분할 영역은 결합이 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{\displaystyle {}_{}}$ b ${\$ 세트 P ${\displaystyle r_{}}$ ${\$} 세트 P r {\displaystyle P_{r$}}$가 있다.$평면$을 n {\$displaystyle$ $n$$}$ 영역으로$$ 분할하여 각 영역에 파란색 $점$의 1/$n$과 빨간색 $점$의 1/$n이$대략적으로 포함되도록 하십시오$.$여기:

• 케이크 C는 전체 평면 $R{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$ ${\$;
• 매개변수 P는 두 점 집합이다.
• 목표함수 G는

${\displaystyle G(X_{1},\dots,X_{n}):=\max \{1,\dots,n\}}\왼쪽(\왼쪽 {p_{b}\cap X_{i} - P_{b}\cap X_{b}} - P_{n}}}\frac 왼쪽 {\p_{r}\cap X_{i} -{n}}} -{n} 오른쪽 \ri}}$

각 영역에 각 색상의 포인트 중 $정확히$ 1 /${\displaystyle n}$ ${\displaystyle$1/$n}$이(가) 있는 경우 0과 같다.

관련 문제

• 보로노이 다이어그램은 지도 세그먼트화 문제의 특정 유형이다.
• 케이크가 2차원일 때 공정한 케이크 커팅은 힐-벡 토지 분할 문제처럼 케이크가 2차원일 때 또 다른 구체적인 지도 세분화 문제다.
• 더 스톤-투키 정리는 특정 지도 세분화 문제와 관련이 있다.

참조