Dynamic Data Structures for Geometric Search and Retrieval

Abstract

Data structures for geometric search and retrieval are of significant interest in areas such as computational geometry, computer graphics, and computer vision. The focus of this dissertation is on the design of efficient dynamic data structures for use in approximate retrieval problems in multidimensional Euclidean space. A number of data structures have been proposed for storing multidimensional point sets. We will focus on quadtree-based structures. Quadtree-based structures possess a number of desirable properties, and they have been shown to be useful in solving a wide variety of query problems, especially when approximation is involved. First, we introduce two dynamic quadtree-based data structures for storing a set of points in space, called the quadtreap and the splay quadtree. The quadtreap is a randomized variant of a quadtree that supports insertion and deletion and has logarithmic height with high probability. The splay quadtree is also a quadtree variant, but this data structure is self-adjusting, that is, it rebalances itself depending on the access pattern. It supports efficient insertion and deletion in the amortized sense. We also study how to dynamically maintain an important geometric structure, called the well-separated pair decomposition (WSPD). A set of n points defines O(n^2) pairs. Callahan and Kosaraju introduced the WSPD as a concise method for approximating the set of all pairs by using only O(n) subsets of pairs that are spatially well-separated from each other. We present the first output sensitive algorithm for maintaining a WSPD for a dynamic point set, that is, one in which the running time depends on the actual number of newly created (or newly destroyed) pairs. Finally, we consider maintaining a data structure for points in motion. Motion is often presented incrementally in discrete time steps, and future motion may not be predictable from the past. This is called the black-box model. We present efficient online algorithms for maintaining two important geometric data structures for moving points in the black-box model, namely nets and net trees. We establish the efficiency of these online algorithms through a competitive analysis.