[알고리즘] Convex Set과 특징

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)`이기 때문이다.