기본 개념
키네틱 데이터 구조는 연속적으로 움직이는 기하학적 시스템의 속성을 추적하기 위해 구현된 데이터 구조로 정의됩니다. 예를 들어, 운동 볼록 껍질 데이터 구조는 n개의 이동 점 그룹의 볼록 껍질을 추적합니다.
운동 데이터 구조의 개발은 로봇 공학, 애니메이션 또는 컴퓨터 그래픽의 충돌 또는 가시성 감지와 같이 연속 동작하는 물리적 개체와 관련된 계산 기하학 문제에서 영감을 받았습니다.
개요
Kinetic 데이터 구조는 시간의 함수로 호출되는 방식으로 변경되는 값 집합이 있는 시스템에서 구현됩니다. 따라서 시스템에는 몇 가지 값이 있으며 각 시스템 값 v에 대해 v=f(t)임을 나타냅니다. 운동 데이터 구조는 현재 가상 시간 t에서 시스템에 대한 쿼리와 두 가지 추가 작업을 허용합니다.
- advance(t):시간 t까지의 시스템이 진행됩니다.
- change(v,f(t)):현재 시간을 기준으로 v 값에서 f(t)까지의 궤적이 변경됩니다.
추가 작업을 지원할 수 있습니다. 예를 들어, 운동 데이터 구조는 종종 점 세트로 구현됩니다. 이 경우 구조는 일반적으로 포인트를 삽입하고 삭제할 수 있도록 합니다.
기존 데이터 구조와 대조
운동 데이터 구조는 저장된 값이 시간에 따라 지속적으로 변경되도록 합니다. 원칙적으로 이것은 고정된 시간 간격으로 점의 위치를 샘플링하고 각 점을 삭제하고 "정적"(전통적인) 데이터 구조에 다시 삽입하여 근사화할 수 있습니다. 그러나 이러한 접근 방식은 구현되는 시간 간격에 따라 오버샘플링 또는 언더샘플링에 취약하며 계산 리소스를 낭비할 수도 있습니다.
인증서 접근 방식
운동 데이터 구조를 구축하기 위해 다음과 같은 일반적인 접근 방식을 구현할 수 있습니다.
- 현재 시간 t에서 시스템의 데이터 구조가 저장됩니다. 이 데이터 구조는 현재 가상 시간에 시스템에 대한 쿼리를 허용합니다.
- 인증서가 있는 데이터 구조가 추가되었습니다. 인증서는 데이터 구조가 정확한 조건으로 취급됩니다. 이제 인증서는 모두 사실이며 데이터 구조는 인증서 중 하나가 더 이상 사실이 아닌 경우에만 완벽하거나 정확하지 않습니다.
- 각 인증서의 실패 시간이 계산되어 더 이상 참이 되지 않는 시간입니다.
- 우선 순위 대기열의 인증서는 실패 시간에 따라 키가 지정되어 저장됩니다.
- 시간 t로 진행하려면 우선순위 큐에서 실패 시간이 최소인 인증서를 확인합니다. 시간 t 이전에 인증서가 실패하면 큐에서 인증서를 삭제하거나 팝하고 실패 시 완벽하거나 정확하도록 데이터 구조를 수정하고 인증서를 업데이트합니다. 우선 순위 대기열에서 가장 낮은 실패 시간을 가진 인증서가 시간 t 이후에 실패할 때까지 이를 반복합니다. 우선 순위 대기열의 최소 실패 시간이 있는 인증서가 시간 t 이후에 실패하면 데이터 구조가 시간 t에서 쿼리에 올바르게 응답할 수 있도록 모든 인증서가 시간 t에서 true로 선언됩니다.
이벤트 유형
인증서 실패는 "이벤트"로 표시됩니다. 이벤트 발생 시 키네틱 데이터 구조에 의해 유지되는 속성이 변경되지 않으면 이벤트는 내부 이벤트로 선언됩니다. 이벤트 발생 시 데이터 구조에 의해 유지되는 속성이 변경되면 이벤트가 외부로 선언됩니다.
성능
인증서 접근 방식을 구현할 때 4가지 성능 측정이 있습니다. n의 다대수 함수이거나 무작위로 작은 €에 대해 O(n€)인 경우 수량을 작다고 합니다. 여기서 n은 객체 수로 처리됩니다.