Publication Type
Journal
Journal Name
Communications in Computational Physics
Publication Date
Page Numbers
545 to 576
Volume
2
Issue
3
Abstract
The need to perform spatial queries and searches is commonly encountered within the
field of computational physics. The development of applications ranging from scientific visualization
to finite element analysis requires efficient methods of locating domain objects relative to general
locations in space. Much of the time, it is possible to form and maintain spatial relationships
between objects either explicitly or by using relative motion constraints as the application evolves
in time. Occasionally, either due to unpredictable relative motion or the lack of state information,
an application must perform a general search (or ordering) of geometric objects without any explicit
spatial relationship information as a basis.
If previous state information involving domain geometric objects is not available, it is typically an
involved and time consuming process to create object adjacency information or to order the objects
in space. Further, as the number of objects and the spatial dimension of the problem domain is
increased, the time required to search increases greatly. This paper proposes an implementation of a
spatial k-d tree (skD-tree) for use by various applications when a general domain search is required.
The skD-tree proposed in this paper is a spatial access method where successive tree levels are
split along different dimensions. Objects are indexed by their centroid, and the minimum bounding
box of objects in a node are stored in the tree node. The paper focuses on a discussion of efficient and
practical algorithms for multidimensional spatial data structures for fast spatial query processing.
These functions include the construction of a skD-tree of geometric objects, intersection query,
containment query, and nearest neighbor query operations.