"Spatial ID" is a geospatial standard that recursively divides the Earth into 3D voxels. By reducing 3D overlap detection to simple set operations, it has strong potential for use in 3D drone airspace management. To safely manage dense drone traffic and identify available airspace, executing fast spatial set operations (e.g., union, intersection, and difference) across a large number of 3D regions is critical. However, practical deployment faces significant computational challenges.

First, representing irregular 3D shapes leads to substantial data bloating. Second, performing set operations across datasets with different resolutions (zoom levels) results in exponential growth in computational complexity.

In this presentation, we propose a novel algorithm to overcome these bottlenecks.

First, we introduce the “Extended Spatial ID.” Unlike standard Spatial IDs, which use a uniform zoom level across all dimensions, our approach assigns independent zoom levels to the X, Y, and Z axes. This significantly compresses the data structure. Based on this design, we developed efficient one-to-one spatial operations. For example, when computing the difference between two regions, our algorithm minimizes the number of resulting voxels. This effectively resolves both data expansion and computational overhead in one-to-one operations.

Second, we introduce "V-Bit" encoding to address the O(N) linear scan bottleneck when detecting overlapping regions in vast datasets. This method encodes the binary tree structure of Spatial IDs into a compact 2-bit array, enabling direct mapping of complex 3D geometries to a 1D ordered index. This encoding facilitates the efficient retrieval of relevant spatial regions using simple prefix range queries in a standard key–Value Store (KVS).

By combining efficient one-to-one spatial operations with fast 1D KVS-based search, our method achieves highly scalable 3D spatial computation for future drone infrastructure.