Use of the Spatial KD-Tree in Computational Physics Applications (Communications in Computational Physics, 2007)
The need to perform spatial queries and searches is commonly encounteredwithin the field of computational physics. The development of applications rangingfrom scientific visualization to finite element analysis requires efficient methods of locating domain objects relative to general locations in space. Much of the time, it ispossible to form and maintain spatial relationships between objects either explicitlyor by using relative motion constraints as the application evolves in time. Occasionally, either due to unpredictable relative motion or the lack of state information, anapplication must perform a general search (or ordering) of geometric objects withoutany explicit spatial relationship information as a basis. If previous state informationinvolving domain geometric objects is not available, it is typically an involved andtime consuming process to create object adjacency information or to order the objectsin space. Further, as the number of objects and the spatial dimension of the problemdomain is increased, the time required to search increases greatly. This paper proposesan implementation of a spatial k-d tree (skD-tree) for use by various applications whena general domain search is required. The skD-tree proposed in this paper is a spatialaccess method where successive tree levels are split along different dimensions. Objects are indexed by their centroid, and the minimum bounding box of objects in anode are stored in the tree node. The paper focuses on a discussion of efficient andpractical algorithms for multidimensional spatial data structures for fast spatial queryprocessing. These functions include the construction of a skD-tree of geometric objects,intersection query, containment query, and nearest neighbor query operations.