## 7.2 GEOMETRICAL RELATIONS IN URBAN SIMULATION

In the course of simulating urban service systems, questions of the following type arise repeatedly:
 1 Given the coordinates of an incident requiring dispatching of a service unit, in which geographical or administrative subdivision did this incident occur? 2 Which of an agency's available service units is the closest one (in terms of travel distance or travel time) to a request for assistance? 3 Which ambulance zones have areas in common with a particular police precinct? 4 Which city blocks lie closest to each one of a new set of voting centers, so that voters can be assigned to the voting precinct most convenient to them? 5 Which ZIP-code areas in a city contain segments of a particular highway or railroad? 6 Given that a refuse incinerator is to be installed at a particular location and that it has a certain geometrically described pattern of smoke dispersal, which voting districts will be affected by the pollutants? 7 Which geographical subdivisions of a city have overlapping parts with the various noise contours (reflecting different noise levels) that will result from a new runway that the local airport authority is contemplating?

These questions and many others of a similar nature are obviously concerned with two-dimensional geometrical relations in urban environments. Most of them could be answered by inspection by a person equipped with a detailed map. However, the computer does not possess the visual and conceptual capabilities of human beings and so must be "told" in precise algorithmic terms how to answer these questions. It is important, moreover, that these algorithms be as efficient as possible, for it may be necessary for a computer to answer questions such as (1) or (2) above, several million times in the course of a typical set of simulation experiments.

In this section we shall discuss such techniques and algorithms. Most of them are of interest by themselves, independently of the simulation context, for they can be used with any computer package that processes geographically oriented data (e.g., "GEO-CODED" data). We shall begin our presentation with a seemingly unrelated problem, that of sorting a list of numbers and of searching through that list.