1. Convex Set
Convex Set이란, 집합 `S`에 포함된 어느 두 점 `p`, `q`를 선택하여 점들을 연결하는 직선을 모두 포함하는 덩어리를 의미한다.
즉, 특정 점들의 집합이 아닌, 이를 감싸고 있는 공간이라고 생각하면 된다. 아래의 그림 3개를 보자
.
그림 1, 출처 : 위키피디아
그림 2, 출처 : 위키피디아
첫번째 그림은 어느 두점 `x`,` y`를 선택하더라도 포함된다. 따라서 convex set이다. 반면 그림 2는 직선중 일부가 Set에 포함되지 않는다. 따라서 Convex Set이 아니다.
2. Convex Set의 Intersection
Convex Set `A`와 `B`가 있고, 이 둘 사이의 교집합은 Convex Set일까? Yes, `A`와 `B`의 교집합이라더라도, 각각 `A`와 `B`에 포함되는 영역이다. 따라서 교집합도 Convex Set이다. (만약 아니라면, basis가 모순이기 때문에 참이다.)
3. Convex Set의 Maximum Distance
Convex Set `A`에 포함된 점들 사이의 거리중에 가장 긴 거리가 되는 두 점은 Convex Hull에 포함될까?
Yes, 만약 거리가 가장 긴 두 점 `p`, `q`라고 하고, 이 점들이 Convex Hull 위에 있다고 하자. 만약 이 중에 점 `q`이 Convex Hull이 아니라고 한다면 반드시 이 점 `q`을 둘러싸는 Convex Hull이 존재한다.
이는 이 점 `q` 보다 외곽에 있음을 뜻한다. 따라서 반드시 두 점 `p`, `q`는 Convex Hull상에 존재한다. (Convex Hull을 모른다면, 이 링크를 먼저 보길 권한다.[알고리즘] Convex hull과 Graham’s scan )
4. Convex Set과 Convex Hull
Convex Hull을 만드는데 시간은 항상 `O(nlogn)`인가? 사실 이것은 잘 모르겠다. 정렬이 된 상태면, 한번만 스캔하면 되므로 `O(n)`이고, 만약 아니라면 정렬을 위한 시간복잡도 `O(nlogn)`이기 때문이다.
'프로그래밍 > 컴퓨터 알고리즘' 카테고리의 다른 글
[알고리즘] 시간 복잡도, 점근적 분석법 그리고 표기법 (0) | 2019.04.14 |
---|---|
[알고리즘] Convex hull과 Graham's scan (0) | 2019.04.14 |
[알고리즘] 그래프 - 플로이드 와샬 (0) | 2019.04.06 |
[BOJ] 11780 - 플로이드 2 풀이 (0) | 2019.04.06 |
[BOJ] 11943 - 파일 옮기기 풀이 (0) | 2019.04.04 |