Geometric retrieval and range searching are fundamental computational problems. A large set of points is given in multi-dimensional space, and the problem is to preprocess these points so that it is possible to count or report the number of points lying inside a given query range. This problem has wide ranging applications in science in areas such as knowledge discovery, pattern recognition, and data compression. Although this is well studied, its computational complexity is quite high. Preliminary work by the investigator and his collaborators has shown that approximation can result in considerably faster running times, but there are still many issues that remain to be understood. The goal of this research is to systematically study the computational complexity of approximate range searching.
This research will study how the computational complexity of range searching depends on various elements of the problem's formulation, including geometric characteristics of the range space (such as smoothness and sharpness) and properties of the semigroup (such as integrality and idempotence). The investigators will study range searching through the development of efficient algorithms and data structures, derivation of lower bounds, and exploration of space-time trade-offs. The intellectual merit of this research his research stems from a deepening understanding of the computational complexity of exact and approximate range searching and the discovery of new, more efficient computational solutions. The broader impacts include the production of new efficient software systems for approximate range searching, which will serve to advance the state of the art in applications areas, and the production of instructional materials on range searching, which will be made available over the web.
