Prerequisites: Graphs, Routes, and Computational Complexity

Since the spatial search problem explicitly deals with alternatives distributed in two-dimensional space, we need a way to characterize the spatial layout of the problem. This links our problem to graph theory and the related theories of optimal routing and computational complexity. In this chapter we do not intend to provide a comprehensive introduction to any of these theories (for such an introduction see e.g. Gibbons, 1985; Parker and Rardin, 1988; Bondy and Murty, 1976). We will discuss only those aspects of these theories that are essential for our discussion of the spatial search problem.