점 집합에 특수 점 k가 있는지 확인하기 위해 알고리즘에 대한 하한을 n 로그 n 시간으로 지정합니다. A의 모든 지점 (M)에 대해, K는 선분 MQ 등을 중간에 있다는 등의 점 Q가 있다면, 포인트들의 세트 A의O (n log n) 시간에 특수 점 k를 찾는 알고리즘
:
K는 다음과 같이 정의된다 ak는 A에 속할 필요는 없습니다.
예를 들어,이 세트에는 4 개의 점 (1,0), (0,1), (0,1)의 집합에 대해 특수 점 k = 1,1), (0,0)이다.
나는 그들이 내게이 질문을 할 때 완전히 부딪혔다. 아무 것도 내 마음에 들지 않았다. 나는 그것이 강한 기하학적 배경을 필요로한다고 생각한다.
O(nlogn) 솔루션 (I는. 여전히 당신이 낮은 바운드 솔루션을 찾고있는 이유는 명확하지 않다 당신은 단지 철저한 점검을뿐 아니라 할 수도 있고, 그럼 그냥 하한의 확인하기 위해 nlogn 루프를 실행 당신이 상한을 의미해야한다고 생각합니다.) :
모든 포인트를 평균하여 유효한 후보 포인트를 찾습니다. 나는. 그들의 좌표를 합산하고 포인트 수로 나눈다. 그러한 k가 존재한다면, 이것이 그 것이다. 그러한 k가 존재하지 않으면 마지막 단계에서 찾은 점이 유효하지 않음을 알 수 있습니다.
점의 새 배열 (집합)을 만듭니다. 여기에서 우리는 점을 중심으로 중심점을 이동합니다. 나는. K = (X K, Y, K ), 점 (X, Y)가 될 것인지 (X-X K, Y-Y K). 비율 x/y와 표준 sqrt (x + y)에 따라 포인트를 정렬하십시오. 다음 단계에서 알 수 있듯이이 정렬이 어떻게 수행되는지는 중요하지 않습니다. 즉 어떤 것이 주요 기준이고 어떤 것이 보조인지는 중요하지 않습니다.
우리는 각 점의 보수를 찾거나 더 나은 방법으로 단순히 배열을 가로 지르고 두 개의 인접한 점이 실제로 보완 적인지 확인합니다. 나는. 이것이 솔루션이라면 우리는 우리의 축을 중심에 놓았 기 때문에이 새로운 배열의 두 보완적인 점은 모두 (x, y)와 (-x, -y) 형태입니다. 즉, 동일한 비율 ("gradient") 그리고 규범, 그리고 종류 후에, 인접해야한다.
k가 유효하지 않다면 우리가이 순회에 도착할 지점이 있으며 이웃이 올바른/보완 형이 아님을 알게됩니다. ==> 그러한 k가 없습니다. 각각의 새로운 점 때문에, 새로운 배열을 구축하기위한 후보 K +
O(n)를 찾는
시간 =
O(n)은 O에서 계산 될 수있다 (1)를 검증하기위한 정렬 +
O(n) 대 +
O(nlogn) 가로 지름
= O(nlogn)
나는 질량 중심을 계산하고 (중복을 먼저 제거한) 귀하의 k인지 확인하고 싶습니다. 아마도 그것이 O(n log n)이 될 유일한 원인은 지정된 위치에서 포인트를 검색하는 것입니다.
나는 당신의 질문을 정말로 이해하지 못합니다. 하한을 찾아내는 알고리즘?* 낮은 * 범위의 알고리즘 *을 의미합니까? 또는 그런 알고리즘 *이 그런 낮은 경계를 가지고 있다는 증거? – davin