Half Plane Intersection

$ax+by+c\geq 0$ 꼴로 표현되는 반평면을 생각해 보자.

이러한 반평면이 여러 개 모이면 아래 진한 부분처럼 볼록 다각형 모양의 교집합이 만들어진다.

(편의상 모든 반평면의 경계선 기울기는 서로 다르다고 가정하자.)

반평면들의 교집합을 구하는 알고리즘에 대해 살펴보겠다.

1. $O(n^3)$

관찰해보면, 교집합의 꼭짓점은 항상 두 경계선의 교점에 해당한다는 것을 알 수 있다.

따라서 모든 경계선 쌍의 교점을 후보로서 탐색한다. $O(n^2)$

교집합에 포함되려면 모든 반평면 부등식($a_ix^{*}+b_iy^{*}+c_i\geq 0$)을 만족해야 하므로, 각각의 교점에 대해 $n$개의 부등식을 조사한다. $O(n)$

그러므로 총 시간복잡도는 $O(n^3)$이다. 구현이 매우 직관적이고 쉽기 때문에 $n$범위가 작을 경우 유용하다.

2. $O(nlogn)$

교집합이 볼록 다각형이라는 점을 상기해보면 convex hull trick과 비슷한 알고리즘을 짤 수 있다.

convex hull trick과 다른 점은 stack 대신 deque를 사용한다는 점, 모든 반평면 삽입 후 후처리가 약간 필요하다는 점이다.

알고리즘은 다음과 같다.

1. 모든 반평면을 경계선의 각도 순으로 정렬한다.

2. 첫 번째 반평면과 두 번째 반평면을 deque에 삽입한다.

3. 세 번째 ~ $n$번째 반평면을 순회하며 다음을 반복한다.

3-1-1. deque.size >= 2이면 deque 맨 뒤에 위치한 두 반평면의 경계선 교점을 계산한다.

3-1-2. 만약 교점이 현재 삽입하려는 반평면에 포함되지 않는다면 deque.pop_back 후 3-1-1로 돌아간다.

3-2. deque에 현재 반평면을 삽입한다.

4-1. deque.size >= 2이면 deque 맨 뒤에 위치한 두 반평면의 경계선 교점을 계산한다.

4-2. 만약 교점이 deque 맨 앞에 위치한 반평면에 포함되지 않는다면 deque.pop_back 후 4-1로 돌아간다.

5-1. deque.size >= 2이면 deque 맨 앞에 위치한 두 반평면의 경계선 교점을 계산한다.

5-2. 만약 교점이 deque 맨 뒤에 위치한 반평면에 포함되지 않는다면 deque.pop_front 후 5-1로 돌아간다.

6. deque.size < 3이면 교집합은 존재하지 않는다. 종료.

7. deque를 순회하며 인접한 반평면의 교점들을 구해 리턴.

여기서 후처리라 한 것은 4~5 과정을 말한다. 사실 이 과정을 위해 deque을 사용한 것인데, 반평면 교집합은 circular list로 관리되어야 하므로 맨 앞/뒤 반평면에 대한 조건을 추가적으로 확인하는 것이다.

나머지 과정은 convex hull trick과 똑같다.

응용 문제

볼록 다각형의 내접원을 구할 때 반평면 교집합을 활용할 수 있다.

각 변을 같은 속도로, 안쪽으로 평행이동시키면 언젠가는 다각형이 소멸되는 지점이 생기는데 거기가 내접원의 중심이다.

회색으로 표시된 자취를 straight skeleton이라 한다.

따라서 변이 이동한 거리 d를 변수로 놓고 교집합의 존재 여부를 판단하는 파라메트릭을 돌리면 된다.

제주도 - https://www.acmicpc.net/problem/3903

제주도 가고싶다

비슷한 문제로 동일한 원 2개를 넣을 수 있는 최대 반지름을 구하는 문제가 있다.

2 circles - https://www.acmicpc.net/problem/5255