home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

Kinetic Data Structures (โครงสร้างข้อมูลแบบจลน์)

แนวคิดพื้นฐาน

Kinetic Data Structure (KDS) คือโครงสร้างข้อมูลที่ติดตาม Attribute (ลักษณะ) ของ Geometric System (ระบบเรขาคณิต) ที่เคลื่อนที่ต่อเนื่อง ตัวอย่าง: Kinetic Convex Hull ติดตาม Convex Hull ของจุดเคลื่อนที่ n จุด

พัฒนาจากปัญหา Computational Geometry ที่เกี่ยวกับวัตถุเคลื่อนที่ต่อเนื่อง: Collision Detection, Visibility ใน Robotics, Animation, Computer Graphics

ภาพรวม (Overview)

KDS ใช้กับระบบที่ค่าเปลี่ยนตามฟังก์ชันของเวลา v = f(t) รองรับ 3 Operation:

  1. Query at time t: ถามสถานะระบบ ณ เวลา t
  2. advance(t): ขยับเวลาระบบไปยัง t
  3. change(v, f(t)): เปลี่ยน Trajectory ของค่า v เป็น f(t) ใหม่

รองรับเพิ่มเติม: Insert/Delete Points

ความแตกต่างจาก Traditional Data Structures

Traditional: ค่าคงที่ KDS: ค่าเปลี่ยนต่อเนื่องกับเวลา
ประมาณด้วย Sampling (Sample แล้ว Delete/Re-insert ใน Static Structure) แต่มีปัญหา: Oversampling/Undersampling, เผาฟื้อทรัพยากร

Certificate Approach (วิธีใบรับรอง) - เทคนิคหลัก

  1. เก็บ Data Structure ณ เวลา t ปัจจุบัน (รองรับ Query)
  2. เพิ่ม Certificates = เงื่อนไขที่ทำให้ Data Structure ถูกต้อง Certificates ทั้งหมด True อยู่ตอนนี้ จะ False เมื่อโครงสร้างผิด
  3. คำนวณ Failure Time ของแต่ละ Certificate (เวลาที่จะกลายเป็น False)
  4. เก็บ Certificates ใน Priority Queue เรียงตาม Failure Time
  5. Advance to time t: ดู Certificate ที่ Failure Time น้อยสุด ถ้าก่อน t → Pop, Fix Data Structure, Update Certificates ทำซ้ำจน Certificate แรก Fail หลัง t → ตอบ Query ได้ถูกต้อง

ประเภท Events (Certificate Failures)

  • Internal Event: Property ที่ KDS Maintain ไม่เปลี่ยน (เช่น โหนดสลับที่ใน Heap)
  • External Event: Property เปลี่ยน (เช่น Convex Hull เปลี่ยนรูป)

Performance Measures (4 ตัวชี้วัด)

Quantity ถือว่า "Small" ถ้าเป็น Polylogarithmic ใน n หรือ O(n^ε) สำหรับ ε เล็กมาก (n = จำนวนวัตถุ)

  1. Responsiveness: เวลาในการจัดการ Event หนึ่งครั้ง (ควร Small)
  2. Efficiency: จำนวน Events ทั้งหมด / จำนวน Events ที่จำเป็นขั้นต่ำ (ควรใกล้ 1)
  3. Locality: จำนวน Certificates ที่เกี่ยวข้องกับ Object หนึ่ง (ควร Small)
  4. Compactness: ขนาด Data Structure / ขนาดข้อมูล Input (ควร Small)

การประยุกต์ใช้

  • Collision Detection ใน Game/Robotics
  • Animation & Computer Graphics
  • Computational Geometry (Closest Pair, Convex Hull, Delaunay Triangulation)
  • GIS & Moving Object Databases