{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "dataset": {
        "id": 490,
        "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": 1,
        "created_at": 1781275786,
        "updated_at": 1781275786
    },
    "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 \u2264 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"
            }
        ]
    }
}