방사형 스윕 구현

Question

2D 평면에서 N 점을 지정 했으므로 적어도 M 점이 포함 된 원의 최소 반경을 찾아야합니다. 내가 사용하고

접근 : -

내가 원의 반경이 이진 검색을 수행합니다.

주어진 집합에서 임의의 점 P를 선택하십시오. 우리는 P를 "회전축"(관례 상 반 시계 방향)으로 사용하여 반경 R을 가진 원 C를 회전합니다. 즉, 회전 중에 언제든지 C가 P에 닿도록 유지합니다. C가 회전하는 동안 우리는 C가 포함하는 포인트의 수를 세는 카운터를 유지합니다.

이 카운터는 어떤 포인트 Q가 원 C의 영역에 들어갈 때만 바뀝니다. 우리의 목표는이 카운터를 증가 (또는 감소)시킬 알고리즘을 제안하는 것입니다. ≠ P는 C의 영역을 입력 (또는 남겨 둡니다)

회전하는 원 C의 상태는 단일 매개 변수 θθ로 나타낼 수 있습니다. 여기서 (r, θ)는 원의 중심의 극 좌표입니다 C, P를 극 좌표계의 고정 점으로 선택하면 이 시스템에서 회전 C는 θ를 증가시키는 것을 의미합니다.

다른 점 Q (≠ P)에 대해서, 우리는 C가 Q를 커버하는 θ의 범위를 실제로 계산할 수 있습니다. 공식적으로 말하자면, C는 if (iff) θ∈ [α, β]를 언제든지 둘러 쌉니다.

[α, β] 구간에서 가장 수가있다 θ의 최적 값은 무엇인가

그럼, 지금까지 원래의 문제가 감소 되었는가?

감소 된 문제는 꽤 표준 O (NlogN) 알고리즘으로 해결할 수 있습니다. [3] 이 감소 된 문제는 N 번 (각 점 P에 하나씩), 따라서 시간 복잡도 O (N2logN)로 풀어야한다. 내가 할 수 있어요

은이 단계를 수행하는 방법 : 서로 점 Q (≠ P), 우리가 실제로 C는 Q. 더 공식적으로 넣어 C를 포함하는 θ의 범위를 계산할 수에 대한

을 (iff) θ∈ [α, β]가있을 때마다 Q를 둘러 쌉니다. 그래서 지금까지 원래의 문제는 다음과 같이 줄어 들었습니다. [α, β] 간격이 가장 많은 θ의 최적 값은 무엇입니까?

해당 부분을 구현하는 방법을 제안 해주십시오.

Answer 1

Q 들어가거나 (반경 R로) 원 C를 벗어나면 : P 및 C의 중심 사이

• 거리는 R있다 (항상이므로); 및

• Q 및 C의 중심 사이의 거리에서는 Q 주위 반경 R의 원, 및 P. 주위 반경 R의 원을 그리면도 그래서

을 R은 두 지점되는 Q가 출입 할 때 교차하는 것은 C의 중심입니다.

± θ를 C 중심과 PQ 중심 사이의 각도라고합시다. 그것을 그려 내면 | PQ |/2R = cos (θ)를 쉽게 볼 수 있으므로 찾고있는 각도를 쉽게 찾을 수 있습니다.