티스토리 뷰

공부

가장 먼 두 점 구하기

전명우 2016.07.17 17:20

2차원 좌표 평면에 정수 좌표 (x, y)로 이루어진 서로 다른 점 $N$개가 있다고 하자. 이 점들 중 유클리드 거리계에서 가장 먼 두 점을 $O(N \lg N)$ 시간복잡도로 해결할 수 있다.


Claim 1) 가능한 모든 기울기에 대해, 그 기울기의 직선에 닿는 양 끝 점의 거리 중 최대값이 가장 먼 두 점의 거리다.


증명) $N$개의 점들 중 가장 먼 두 점을 $a$와 $b$라 하자. $a$와 $b$를 잇는 선분을 그리고 수직한 직선을 그렸을 때 아래와 같이 된다.


파란색 직선 위를 포함하여 파란색 영역에 $a$와 $b$ 이외에 다른 점들은 존재하지 않다. 만약 존재한다고 가정하면 $a$와 $b$가 가장 먼 두 점이라는 가정에 모순된다.

따라서 가능한 모든 기울기에 대해, 그 기울기의 직선에 닿는 양 끝 점의 거리만 고려해도 가장 먼 두 점의 거리를 구할 수 있다.


Lemma 1) 임의의 기울기의 직선에 닿는 양 끝 점은 $N$개의 점을 모두 포함하는 볼록껍데기(Convex Hull)의 꼭지점이다.

Lemma 2) 볼록껍데기의 변들에 해당하는 기울기에 대해서만 고려해도 된다.


Lemma 1은 쉽게 증명된다. Lemma 2는 자세한 증명은 생략하지만, 볼록껍데기의 변들에 해당하는 기울기에 대해서만 고려해도 모든 기울기에 대해 고려할 때와 양 끝 점 쌍은 같게 나온다는 사실을 확인하면 된다. 위 두 lemma가 성립하므로 Graham Scan으로 $O(N \lg N)$ 시간안에 볼록껍데기를 구하고, $O(N)$ 시간안에 가장 먼 두 점을 구할 수 있다.


코드 보기


저작자 표시
신고

'공부' 카테고리의 다른 글

트리의 지름 구하기  (0) 2016.10.11
Convex Hull Optimization  (4) 2016.08.23
가장 먼 두 점 구하기  (4) 2016.07.17
Building Heap in Linear Time  (2) 2016.07.01
String Matching Algorithm  (4) 2016.06.24
Persistent Segment Tree  (4) 2016.06.23
댓글
  • 프로필사진 질문자 // Farthest two point
    아래의 코드에서 i 번째 점으로 부터 가장 먼 점을 구하는거 같은데..
    순차적으로 저렇게 검사하면 O(n^2)아닌가요?? 주어진 점들이 원의 형태로 있다고 햇을때 convex hull은 무의미 할테고...
    2017.01.03 16:59 신고
  • 프로필사진 hongjun7 기하적 특성상 ccw 방향이 바뀌는 지점이 단조롭게 이동하기 때문에(시계, 혹은 반시계 방향으로 감소하지 않고 증가), O(N)입니다. 2017.01.11 15:21 신고
  • 프로필사진 leeehosu01 죄송하지만 변을 기준으로 하면 점과 점 사이의 거리와는 조금 다를 수 있지 않나요? 2017.05.07 09:55 신고
  • 프로필사진 전명우 질문이 이해되지 않습니다. 2017.07.26 12:00 신고
댓글쓰기 폼