บทนำ: จาก 1D ไปสู่ Multi-D
Spatial Search Structures มาจากไอเดียเดียวกับ Symbolic Data (เช่นรายชื่อ) ในยุค 60-70s: เรียงลำดับ + Binary Search = O(log n) แทน O(n) ของ Sequential Search
ถ้าต้องการ Insert/Delete พร้อมรักษาลำดับ → ต้องใช้ Dynamic Structure (Pointers) → Binary Search Tree (BST)
BST บน Real Line (1D)
BST แทน Set ของ Integers A = {1,2,5,6,7,9} บน Real Line
ค้นหาจุด: Insert จุด → ตาม Path ของ Nested Intervals ที่มีจุด → Balanced Tree = O(log n) Steps
Tree เอง Encode ส่วนของ Search Algorithm (ตัดสินใจลำดับการค้นหา)
Partitioning Trees = Generalization ของ BST ไป Multi-D
- สร้าง Partitioning Tree ≈ Geometric Version ของ Quick Sort
- Insert/Delete = Merge Trees ≈ Merge Sorted Lists ใน Merge Sort
- แตกต่าง: จุดใน >1D ไม่แบ่ง Space ได้ → ต้องใช้ Hyperplanes แทน
- Hyperplanes แบ่ง Region เป็น 2 Half-spaces เสมอ ไม่ว่าจะกี่มิติ
สรุป
BSP Trees นำแนวคิด BST (1D) ขยายไป Multi-D โดยใช้ Hyperplanes แทน Points การ Partition แบบ Recursive สร้างโครงสร้างที่รองรับ Spatial Queries ได้อย่างมีประสิทธิภาพ
