Geometric searching with spacefilling curves
William Glenn Nulty · SMARTech Repository (Georgia Institute of Technology) · 1993
Data searching is locating a desired subset of data items in a collection of data. Geometric searching problems are a class of problems where the data items and search conditions are geometric objects (such as points, lines, regions, or networks), and are fundamental problems in spatial decision support systems. Traditional data structures organize data for efficient (and dynamic) one--dimensional searching, but generally do not extend gracefully to multidimensional geometric problems. Spacefilling curves are mathematical tools with two inviting properties for geometric searching: the curves organize data in multidimensional space, and collapse the organization to a single dimension. Thus spacefilling curves equip traditional data structures with multidimensional search capabilities. We develop a framework for geometric searching with spacefilling curves, unifying results from the fields of operations research, computational geometry, and computer science. We introduce the Sierpinski spacefilling curve and an elegant searching algorithm for searching a database of geometric objects, offering a simple geometric searching approach with good clustering properties. We analyze the performance of geometric searching with spacefilling curves for planar and higher--dimensional orthogonal range searching, planar circular region searching, and planar polygon searching. We also show search work is proportional to the size of planar query objects, and analyze the number of spacefilling curve clusters intersecting orthogonal range queries. We provide a probabilistic analysis for planar orthogonal range searching, establishing a relationship between curve clusters and search precision. We parameterize the searching algorithm, adapting the search strategy to query object properties and computer storage environments.