แนวคิดพื้นฐาน
โครงสร้างข้อมูลจลนศาสตร์ถูกกำหนดให้เป็นโครงสร้างข้อมูลที่นำไปใช้เพื่อติดตามแอตทริบิวต์ของระบบเรขาคณิตที่เคลื่อนที่อย่างต่อเนื่อง ตัวอย่างเช่น โครงสร้างข้อมูลของเปลือกนูนจลนศาสตร์ติดตามตัวเรือนูนของกลุ่มจุดเคลื่อนที่ n จุด
การพัฒนาโครงสร้างข้อมูลจลนศาสตร์ได้รับแรงบันดาลใจจากปัญหาเรขาคณิตเชิงคำนวณที่เกี่ยวข้องกับวัตถุทางกายภาพในการเคลื่อนไหวต่อเนื่อง เช่น การชนกันหรือการตรวจจับการมองเห็นในหุ่นยนต์ แอนิเมชั่น หรือคอมพิวเตอร์กราฟิก
ภาพรวม
โครงสร้างข้อมูลจลนศาสตร์ถูกนำไปใช้กับระบบที่มีชุดของค่าที่เปลี่ยนแปลงตามฟังก์ชันของเวลาในรูปแบบที่เรียกว่า ดังนั้นระบบจึงมีค่าบางค่า และสำหรับค่าระบบแต่ละค่า v ก็แสดงว่า v=f(t) โครงสร้างข้อมูลจลนศาสตร์อนุญาตการสืบค้นบนระบบ ณ เวลาเสมือนปัจจุบัน t และการดำเนินการเพิ่มเติมอีกสองรายการ
- ล่วงหน้า(t):ระบบต่อเวลา t เป็นขั้นสูง
- change(v,f(t)):วิถีของค่า v เป็น f(t) ณ เวลาปัจจุบัน มีการเปลี่ยนแปลง
รองรับการทำงานเพิ่มเติมได้ ตัวอย่างเช่น โครงสร้างข้อมูลจลนศาสตร์มักใช้กับชุดของจุด ในกรณีนี้ โครงสร้างมักจะอนุญาตให้แทรกและลบจุดได้
ตรงกันข้ามกับโครงสร้างข้อมูลแบบเดิม
โครงสร้างข้อมูลจลนศาสตร์อนุญาตให้ค่าที่เก็บไว้ในนั้นเปลี่ยนแปลงอย่างต่อเนื่องตามเวลา โดยหลักการแล้ว ค่านี้สามารถประมาณได้โดยการสุ่มตัวอย่างตำแหน่งของจุดต่างๆ ในช่วงเวลาที่กำหนด และลบและใส่แต่ละจุดกลับเข้าไปในโครงสร้างข้อมูล "คงที่" (ดั้งเดิม) อย่างไรก็ตาม วิธีการดังกล่าวมีความอ่อนไหวต่อการสุ่มตัวอย่างมากเกินไปหรือการสุ่มตัวอย่างน้อยเกินไป ขึ้นอยู่กับช่วงเวลาที่มีการใช้งาน และอาจสิ้นเปลืองทรัพยากรในการคำนวณด้วย
แนวทางการรับรอง
วิธีการทั่วไปต่อไปนี้สามารถนำมาใช้เพื่อสร้างโครงสร้างข้อมูลจลนศาสตร์
- โครงสร้างข้อมูลบนระบบ ณ เวลาปัจจุบัน t ถูกจัดเก็บไว้ โครงสร้างข้อมูลนี้อนุญาตการสืบค้นข้อมูลในระบบ ณ เวลาเสมือนปัจจุบัน
- เสริมโครงสร้างข้อมูลพร้อมใบรับรอง ใบรับรองถือเป็นเงื่อนไขภายใต้โครงสร้างข้อมูลที่ถูกต้อง ใบรับรองเป็นจริงทั้งหมดในขณะนี้ และโครงสร้างข้อมูลจะหยุดสมบูรณ์แบบหรือแม่นยำก็ต่อเมื่อหนึ่งในใบรับรองไม่เป็นความจริงอีกต่อไป
- เวลาความล้มเหลวของใบรับรองแต่ละรายการจะถูกคำนวณ เวลาที่จะหยุดเป็นจริง
- ใบรับรองในคิวลำดับความสำคัญถูกจัดเก็บ โดยคีย์ตามเวลาที่ล้มเหลว
- หากต้องการเลื่อนไปยังเวลา t ให้ดูใบรับรองที่มีเวลาล้มเหลวขั้นต่ำจากคิวลำดับความสำคัญ หากใบรับรองล้มเหลวก่อนเวลา t ให้ลบหรือป๊อปออกจากคิวและแก้ไขโครงสร้างข้อมูลเพื่อให้สมบูรณ์หรือแม่นยำในเวลาที่ล้มเหลว และอัปเดตใบรับรอง ทำซ้ำจนกระทั่งและเว้นแต่ใบรับรองที่มีเวลาความล้มเหลวต่ำสุดในคิวลำดับความสำคัญจะล้มเหลวหลังจากเวลา t หากใบรับรองที่มีเวลาล้มเหลวขั้นต่ำในคิวลำดับความสำคัญล้มเหลวหลังจากเวลา t ใบรับรองทั้งหมดจะถูกประกาศเป็นจริง ณ เวลา t เพื่อให้โครงสร้างข้อมูลสามารถตอบคำถามได้อย่างถูกต้อง ณ เวลา t
ประเภทของกิจกรรม
ความล้มเหลวของใบรับรองจะแสดงเป็น "เหตุการณ์" เหตุการณ์จะถูกประกาศเป็นเหตุการณ์ภายในหากคุณสมบัติที่ดูแลโดยโครงสร้างข้อมูลจลนศาสตร์ไม่เปลี่ยนแปลงในเวลาที่เกิดเหตุการณ์ เหตุการณ์จะถูกประกาศเป็นภายนอกหากคุณสมบัติที่ดูแลโดยโครงสร้างข้อมูลเปลี่ยนแปลงในเวลาที่เกิดเหตุการณ์
ประสิทธิภาพ
เมื่อนำแนวทางใบรับรองไปใช้ จะมีการวัดประสิทธิภาพสี่ประการ เราเรียกปริมาณว่าปริมาณน้อย หากเป็นฟังก์ชันพหุลอการิทึมของ n หรือเป็น O(n€) สำหรับ € ขนาดเล็กแบบสุ่ม โดยที่ n ถือเป็นจำนวนอ็อบเจ็กต์
