Algorithms in a restricted universe
Rolf G. Karlsson · 1985
This thesis deals with the design and analysis of algorithms and their associated data structures on a restricted universe of elements. We examine a few fundamental data types, and develop efficient algorithms for their solutions, with time and space complexities being a function of the size of the restricted universe. We present fast static and dynamic algorithms for the dictionary problem, and for the nearest neighbor problem. We develop a lower bound model, the segment graph model, under which we prove the given algorithms optimal. We extend the fast static nearest neighbor search to the plane, when proximity is defined in the L(,1) or L(,(INFIN)) metric (most earlier work involves the L(,2) norm). We also present semidynamic and dynamic proximity algorithms using nearly minimal space in two or more dimensions, under the L(,1) and L(,(INFIN)) metrics. For the array maintenance problem, a range query problem, we provide data structures which minimize the update cost under two design constraints. Finally, we apply some of the algorithms to three optimization problems.