api: "YAML JSON TOON Database"
version: "1.0.0"
format: "json"
dataset:
  id: 59
  slug: "spatial-data-structures"
  title: "Spatial Data Structures"
  description: "Spatial indexing structures for multi-dimensional data: k-d trees, R-trees, quadtrees, octrees, grid files, and space-filling curves (Z-order, Hilbert)."
  category: "Data Structures"
  category_slug: "data-structures"
  tags: "spatial,kd-tree,rtree,quadtree,octree,space-filling-curves,geospatial,nearest-neighbor"
  view_count: 0
  created_at: 1778695229
  updated_at: 1778695229
data:
  structures:
    - name: "k-d Tree (k-dimensional tree)"
      dimensions: "Any k"
      query_time: "O(n^(1-1/k)) average for nearest neighbor"
      space: "O(n)"
      description: "Binary tree alternating split axis at each level; partitions k-dimensional space"
      operations:
        - "nearest neighbor"
        - "range search"
        - "k-nearest neighbors"
      use_cases:
        - "3D graphics (ray tracing acceleration)"
        - "Point cloud processing"
        - "Recommendation systems (k-NN)"
        - "Robotics path planning"
      notes: "Not suitable for high dimensions (curse of dimensionality); best for k ≤ 20"
    - name: "R-Tree"
      dimensions: "2D/3D spatial"
      query_time: "O(log n) average"
      space: "O(n)"
      description: "Balanced tree grouping nearby objects with minimum bounding rectangles (MBRs); optimized for disk storage"
      operations:
        - "range search"
        - "nearest neighbor"
        - "spatial join"
        - "window query"
      use_cases:
        - "GIS systems (PostGIS, SpatiaLite)"
        - "Location-based services"
        - "Game engines (collision detection)"
        - "Database spatial indexes"
      notes: "Variants: R*-tree (better split strategy), R+-tree (no overlap), STR-packed (bulk loading)"
    - name: "Quadtree"
      dimensions: "2D"
      query_time: "O(log n) average"
      space: "O(n)"
      description: "Recursive subdivision of 2D space into 4 quadrants; leaf nodes contain points or regions"
      operations:
        - "point query"
        - "range search"
        - "nearest neighbor"
        - "region query"
      use_cases:
        - "2D game collision detection"
        - "Image compression (quadtree encoding)"
        - "Mesh generation"
        - "Sparse matrix storage"
      notes: "Point quadtree (stores points) vs region quadtree (stores areas); unbalanced without care"
    - name: "Octree"
      dimensions: "3D"
      query_time: "O(log n) average"
      space: "O(n)"
      description: "3D extension of quadtree; recursively subdivides space into 8 octants"
      operations:
        - "point query"
        - "range search"
        - "frustum culling"
        - "collision detection"
      use_cases:
        - "3D game engines (Unreal, Unity)"
        - "Point cloud processing (LiDAR)"
        - "Voxel engines (Minecraft-like)"
        - "3D mesh simplification"
      notes: "Essential for 3D spatial partitioning; often combined with frustum culling for rendering"
    - name: "Grid File"
      dimensions: "2D/low-dimensional"
      query_time: "O(1) for exact match, O(k) for range"
      space: "O(n + grid_size)"
      description: "Uniform grid overlaying space; each cell points to objects within it"
      operations:
        - "point query"
        - "range search"
        - "nearest neighbor"
      use_cases:
        - "Particle systems"
        - "Molecular dynamics"
        - "Simple collision detection"
        - "Real-time physics engines"
      notes: "Simple but suffers from curse of dimensionality; cell size critically affects performance"
    - name: "Z-Order Curve (Morton Order)"
      dimensions: "Any k"
      query_time: "O(log n) with B-tree"
      space: "O(n)"
      description: "Maps multi-dimensional points to 1D by interleaving binary representations; preserves locality"
      operations:
        - "range search via B-tree on Z-values"
        - "nearest neighbor"
      use_cases:
        - "Geohashing (geographic indexing)"
        - "GPU spatial sorting"
        - "Database indexing (HBase, Accumulo)"
        - "Texture memory layout"
      notes: "Can use standard B-tree/B+-tree on Z-values; locality preservation not as good as Hilbert curve"
    - name: "Hilbert Curve"
      dimensions: "2D (extendable)"
      query_time: "O(log n) with B-tree"
      space: "O(n)"
      description: "Space-filling curve with better locality preservation than Z-order; maps 2D to 1D continuously"
      operations:
        - "range search"
        - "nearest neighbor via 1D index"
      use_cases:
        - "Image processing"
        - "Database indexing (better locality than Z-order)"
        - "Distributed hash tables"
        - "Cache-oblivious algorithms"
      notes: "More complex to compute than Z-order but significantly better spatial locality; used in Google S2 Geometry"