O (n log n) 시간에 선 배열의 경계 상자

Question

선 배열의 경계 상자 (평행선 없음)를 계산하고 싶습니다. 경계 상자에는 줄 정렬의 모든 교차점이 포함되어야합니다.

나는 몇 가지 연구를 수행했으며 O (n log n) 시간에서 경계 상자를 계산할 수 있어야한다고 여러 번 발견했습니다. 불행히도이 주장의 출처를 찾을 수 없었습니다.

나는이 문제를 O (n log n) 시간에 해결했지만 지금까지는 할 수 없었던 알고리즘을 생각해 냈습니다. 나는 이중성을 사용하여 봉투를 계산하려고 시도했지만 불행히도 봉투는 항상 최저 및 최고 교차점을 포함하지는 않습니다.

누군가 알고리즘을 찾을 수있는 곳이나 작동 방식을 알고 있다면 감사하겠습니다.

Answer 1

O (n log n) 시간에 수행 할 수 있습니다. 우리는 모든 교차점을 확인할 필요가 없습니다. 단지 가장 높고/낮은 x와 y 좌표를 가진 것을 찾아야합니다.

다음은 내가 생각해 낸 것입니다. 저는 우리가 같은 강연에 있다고 생각합니다. 그리고 이것은 제가 정확히 들어갈 내용입니다. 따라서이 솔루션을 사용하려면 붙여 넣기 만하지 마십시오. 좌측 결합 용

알고리즘 :

1) 점 라인 이중성 (L)에 따른 포인트로 행합니다 MX = Y + C => L * = (m, -C). O (n)

2) x 좌표로 주문하십시오. O (n log n)

3) 가장 낮은 기울기를 가진 선으로 처음 두 점의 선을 저장하십시오. 4) 점들을 통과하고 두 점 P [i]와 P [i + 1]의 선이 이전에 저장된 가장 낮은 기울기보다 낮은 기울기를 갖는 경우 그 선을 가장 낮은 기울기를 가진 선으로 저장합니다. O (n)

5) 이중성을 다시 사용하여 선을 점으로 만듭니다.O (1)

6) 해당 점의 x 좌표를 왼쪽 경계로 반환합니다. O (1)

최저 기울기가있는 선은 가장 낮은 x 좌표와의 교점을 나타냅니다. 오른쪽 경계는 동일하지만 최대 경사로 작동합니다. 상한과 하한에 대한 알고리즘을 얻으려면 다음을 결정할 수 있도록 l : y = mx + c => l * = (-c, m) (기본적으로 평면을 90도 회전)으로 이중성을 변경할 수 있습니다. 슬로프를보고 가장 낮은 교차점과 가장 높은 교차점.

가장 가파른 슬로프를 찾기 위해 선의 모든 교차점을 볼 필요는 없으며, x 좌표에 따라 서로 인접한 선을 보면 충분합니다.

Answer 2

저는 O (n log n) 시간에 경계 상자 계산이 가능해야한다는 것을 여러 번 발견했습니다.

나는 그 전제에 도전한다. n 개의 선이 있으면 O (n^2) 개의 교점을 갖는 경우를 만들 수 있습니다. 모든 교차점을 찾는 그들 주위에 경계 상자를 구축하는 것은 적어도 차 런타임해야한다 ((오메가 N^2)) 순진

당신은 다음과 같은 방법으로 문제에 접근 할 수 :

1. 사용 라인의 모든 교차점을 찾기 위해 Bentley–Ottmann algorithm. k 개의 교점을 갖는 n 개의 선이 주어지면이 알고리즘은 O ((n + k) log n)의 런타임 복잡성을 갖습니다. 교차점이 많은 경우 순진한 알고리즘 (각 쌍의 선 사이의 교차점 계산)이 더 빨라 O (n^2)가 될 수 있습니다.

2. 모든 교차점에서 실행하고 모든 치수의 최소 및 최대를 찾아 모든 교차점의 경계 상자를 검색합니다. 이것은 O (k)의 실행 시간을 갖는다.