빈(컴퓨터 지오메트리)
Bin (computational geometry) | 이 기사는 대부분의 독자들이 이해하기에는 너무 전문적일 수 있다.(2012년 6월 (이 및 에 대해 ) |
계산 기하학에서 빈은 효율적인 영역 쿼리를 허용하는 데이터 구조입니다.데이터 포인트가 빈에 들어갈 때마다 빈의 빈도가 [1]1씩 증가합니다.
예를 들어, 2D 평면에 축으로 정렬된 직사각형이 있는 경우 구조물은 "쿼리 직사각형이 주어진 경우, 이 직사각형이 교차하는 직사각형은 무엇입니까?"라는 질문에 대답할 수 있습니다.위 그림의 예에서 A, B, C, D, E 및 F는 기존의 직사각형이므로 모든 직사각형을 닫힌 간격으로 정의하면 직사각형 Q를 가진 쿼리는 C, D, E 및 F를 반환해야 합니다.
데이터 구조는 2D 평면의 영역을 균일한 크기의 빈으로 분할합니다.빈의 경계 상자에는 조회할 후보 직사각형이 모두 들어 있습니다.모든 빈은 2D 배열로 배열됩니다.모든 후보가 2D 어레이로 표시됩니다.후보 배열의 크기는 후보 배열이 교차하는 빈의 수입니다.
예를 들어 위쪽 그림에서 후보 B는 6개의 빈을 교차시키기 때문에 3행x2열 배열로 6개의 원소가 배열되어 있습니다.각 빈에는 단일 링크 리스트의 선두가 포함되어 있습니다.후보가 빈과 교차하는 경우 빈의 링크 목록에 연결됩니다.후보 배열의 각 요소는 대응하는 빈의 링크 리스트의 링크 노드입니다.
운용
쿼리
쿼리 직사각형 Q에서 빈 경계 상자의 왼쪽 하단 모서리를 Q의 왼쪽 하단 모서리에서 빼고 결과를 각각 빈의 폭과 높이로 나누면 어느 빈의 왼쪽 하단 모서리가 효율적으로 교차하는지 알 수 있다.그런 다음 빈 Q가 교차하는 빈을 반복하고 이러한 빈의 링크된 목록에 있는 모든 후보를 조사할 수 있습니다.각 후보별로 Q와 실제로 교차하는지 확인합니다.이전에 보고되지 않은 경우 보고합니다.후보를 처음 발견했을 때만 보고한다는 관례를 사용할 수 있습니다.후보자를 쿼리 직사각형에 대해 클리핑하고 왼쪽 아래 모서리를 현재 위치와 비교하면 쉽게 이 작업을 수행할 수 있습니다.일치하는 경우 보고하고 일치하지 않는 경우 건너뜁니다.
삽입 및 삭제
1개의 빈에 후보를 삽입하는 시간은 일정하므로 삽입은 후보가 교차하는 빈의 수와 선형입니다.후보자가 교차하는 각 빈의 단일 링크 목록을 검색해야 하므로 삭제 비용이 더 많이 듭니다.
멀티스레드 환경에서는 삽입, 삭제 및 쿼리는 서로 배타적입니다.그러나 전체 데이터 구조를 잠그는 대신 빈의 하위 범위를 잠글 수 있습니다.오버헤드를 정당화하기 위해 상세한 성능 분석을 수행해야 합니다.
효율과 튜닝
분석은 해시 테이블과 유사합니다.최악의 시나리오는 모든 후보가 한 곳에 몰리는 것이다.다음으로 쿼리는 O(n), delete는 O(n), insert는 O(1)입니다.여기서 n은 후보 수입니다.각 빈이 일정한 수의 후보를 가지도록 후보가 균등하게 배치된 경우 쿼리는 O(k)가 됩니다. 여기서 k는 쿼리 직사각형이 교차하는 빈의 수입니다.삽입 및 삭제는 O(m)입니다. 여기서 m은 삽입 후보가 교차하는 빈의 수입니다.실제로 삭제는 삽입보다 훨씬 느립니다.
해시 테이블과 마찬가지로 bin의 효율은 후보와 쿼리의 위치와 크기 분포에 따라 크게 달라집니다.일반적으로 쿼리 사각형이 작을수록 쿼리의 효율이 높아집니다.빈의 크기는 가능한 한 후보를 적게 포함하되 후보가 너무 많은 빈을 스팬하지 않도록 충분히 커야 합니다.후보가 다수의 빈에 걸쳐 있는 경우 쿼리는 교차로의 첫 번째 빈에 보고된 후 이 후보를 반복해서 건너뛰어야 합니다.예를 들어 그림에서 E는 Q의 쿼리에서 4번 방문되므로 3번 건너뜁니다.
쿼리 속도를 높이기 위해 분할을 오른쪽 시프트로 대체할 수 있습니다.이렇게 하려면 축 방향을 따라 있는 빈의 수가 2의 지수여야 합니다.
다른 범위 쿼리 데이터 구조와 비교
k-d 트리에 대해 bin 구조를 사용하면 재조정의 복잡성 없이 효율적으로 삽입 및 삭제할 수 있습니다.이 기능은 검색 데이터 구조에 모양을 점진적으로 추가해야 하는 알고리즘에서 매우 유용할 수 있습니다.
레퍼런스
- ^ Harmony Search Optimization for HDR Prostate Brachytherapy. 2008. ISBN 9780549534365. Archived from the original on 2016-03-06. Retrieved 2016-01-12.
