여러 점의 최대 퍼짐

Question

나는 한 그룹의 점 (x, y)을 가지고 있으며 가장 멀리 떨어져있는 두 점 사이의 거리를 알아야합니다.

이것을 찾는 가장 효율적인 방법은 무엇입니까?

감사

Answer 1

음, 다른 모든 점에 대해 모든 지점을 compairing 확실히 하지 효율적이다.

가장 효율적인 방법은 모든 점을 둘러싸는 볼록 다각형 (각도가 180 이상 없음) 인 볼록 선체를 찾는 것입니다.

그 후, 정반 쌍을 사용하여 선체에서 가장 먼 지점을 찾습니다.

알고리즘은 여기서 설명 :

http://www.seas.gwu.edu/~simhaweb/cs153/lectures/module1/module1.html