Searching in Constant Time and

                                         1  2
			    Minimum Space


		   (Minimae Res Magni Momenti Sunt)



			    Andrej Brodnik



			       Abstract


   This report deals with techniques for minimal space representation
   of a subset of elements from a bounded universe so that various
   types of searches can be performed in constant time. In particular,
   we introduce a data structure to represent a subset of N elements
   of [0, ..., M-1] in a number of bits close to the information-
   theoretic minimum and use the structure to answer membership
   queries in constant time. Next, we describe a representation of an
   arbitrary subset of points on an M x M grid such that closest
   neighbour queries (under L_1 and L_oo) can be performed in constant
   time. This structure requires M^2 + o(M^2) bits. Finally, under a
   byte overlap model of memory we present an M+o(M) bit, constant
   time solution to the dynamic one-dimensional closest neighbour
   problem (hence, also union-split-find and priority queue problems)
   on [0, ..., M-1].

 1 This report is based on the author's PhD thesis. Many results are
   joint work with J. Ian Munro.
 2 Supported in part by the Natural Science and Engineering Research
   Council of Canada under grant number A-8237 and the Information
   Technology Research Centre of Ontario.