티스토리 뷰

공부

가장 먼 두 점 구하기

전명우 2016. 7. 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)$ 시간안에 가장 먼 두 점을 구할 수 있다.



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

트리의 지름 구하기  (6) 2016.10.11
Convex Hull Optimization  (4) 2016.08.23
Building Heap in Linear Time  (2) 2016.07.01
String Matching Algorithms  (5) 2016.06.24
Persistent Segment Tree  (6) 2016.06.23
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함