Khái niệm cơ bản
Cấu trúc dữ liệu động học được định nghĩa là cấu trúc dữ liệu được thực hiện để theo dõi một thuộc tính của hệ thống hình học đang chuyển động liên tục. Ví dụ:cấu trúc dữ liệu vỏ lồi động học theo dõi vỏ lồi của một nhóm n điểm chuyển động.
Sự phát triển của cấu trúc dữ liệu động học được lấy cảm hứng từ các bài toán hình học tính toán liên quan đến các đối tượng vật lý trong chuyển động liên tục, ví dụ như phát hiện va chạm hoặc khả năng hiển thị trong robot, hoạt hình hoặc đồ họa máy tính.
Tổng quan
Cấu trúc dữ liệu động học được thực hiện trên các hệ thống có một tập hợp các giá trị đang thay đổi như một hàm của thời gian, theo một cách gọi là. Vì vậy, hệ thống có một số giá trị, và với mỗi giá trị hệ thống v, nó được biểu thị rằng v =f (t). Cấu trúc dữ liệu động học cho phép các truy vấn trên hệ thống tại thời điểm ảo t hiện tại và hai hoạt động bổ sung
- nâng cao (t):Hệ thống đến thời điểm t là tiên tiến.
- change (v, f (t)):Quỹ đạo của giá trị v đến f (t), tính đến thời điểm hiện tại, được thay đổi.
Các hoạt động bổ sung có thể được hỗ trợ. Ví dụ, cấu trúc dữ liệu động học thường được thực hiện với một tập hợp các điểm. Trong trường hợp này, cấu trúc thường cho phép chèn và xóa các điểm.
Tương phản với cấu trúc dữ liệu truyền thống
Cấu trúc dữ liệu động học cho phép các giá trị được lưu trữ trong nó thay đổi liên tục theo thời gian. Về nguyên tắc, điều này có thể được ước tính gần đúng bằng cách lấy mẫu vị trí của các điểm trong những khoảng thời gian cố định, đồng thời xóa và chèn lại từng điểm vào cấu trúc dữ liệu "tĩnh" (truyền thống). Tuy nhiên, cách tiếp cận như vậy dễ bị lấy mẫu quá mức hoặc lấy mẫu thiếu, tùy thuộc vào khoảng thời gian nào được thực hiện và cũng có thể gây lãng phí tài nguyên tính toán.
Cách tiếp cận chứng chỉ
Cách tiếp cận chung sau đây có thể được thực hiện để xây dựng cấu trúc dữ liệu động học
- Một cấu trúc dữ liệu trên hệ thống tại thời điểm hiện tại được lưu trữ. Cấu trúc dữ liệu này cho phép các truy vấn trên hệ thống tại thời điểm ảo hiện tại.
- Cấu trúc dữ liệu với các chứng chỉ được tăng cường. Chứng chỉ được coi là điều kiện mà theo đó cấu trúc dữ liệu là chính xác. Hiện tất cả các chứng chỉ đều đúng và cấu trúc dữ liệu sẽ chỉ ngừng hoàn hảo hoặc chính xác khi một trong các chứng chỉ không còn đúng nữa.
- Thời gian lỗi của mỗi chứng chỉ được tính toán, thời gian chứng chỉ ngừng đúng.
- Các chứng chỉ trong hàng đợi ưu tiên được lưu trữ, khóa theo thời gian lỗi của chúng.
- Để đến thời điểm t, hãy xem chứng chỉ có thời gian lỗi tối thiểu từ hàng đợi ưu tiên. Nếu chứng chỉ bị lỗi trước thời điểm t, hãy xóa hoặc đưa nó khỏi hàng đợi và sửa cấu trúc dữ liệu để nó hoàn hảo hoặc chính xác tại thời điểm bị lỗi, đồng thời cập nhật chứng chỉ. Lặp lại điều này cho đến khi và trừ khi chứng chỉ có thời gian lỗi thấp nhất trong hàng đợi ưu tiên bị lỗi sau thời gian t. Nếu chứng chỉ có thời gian lỗi tối thiểu trong hàng đợi ưu tiên không thành công sau thời gian t, thì tất cả chứng chỉ được khai báo là đúng tại thời điểm t để cấu trúc dữ liệu có thể trả lời chính xác các truy vấn tại thời điểm t.
Các loại sự kiện
Lỗi chứng chỉ được biểu thị là "sự kiện". Một sự kiện được khai báo là nội bộ nếu thuộc tính được duy trì bởi cấu trúc dữ liệu động học không thay đổi tại thời điểm xảy ra sự kiện. Một sự kiện được khai báo là bên ngoài nếu thuộc tính được cấu trúc dữ liệu duy trì thay đổi tại thời điểm xảy ra sự kiện.
Hiệu suất
Khi thực hiện cách tiếp cận chứng chỉ, có bốn thước đo hiệu suất. Chúng ta gọi một đại lượng là nhỏ nếu nó là một hàm đa thức của n, hoặc là O (n €) cho € nhỏ ngẫu nhiên, trong đó n được coi là số đối tượng.