Voronoi Diagrams

Suppose you are on the advisory board for the planning of a supermarket chain, and there are plans to open a new branch at a certain location. To predict whether the new branch will be profitable, you must estimate the number of customers it will attract. For this you have to model the behavior of your potential customers: how do people decide where to do their shopping? A similar question arises in social geography, when studying the economic activities in a country: what is the trading area of certain cities? In a more abstract setting we have a set of central places—called

sites

—that provide certain goods or services, and we want to know for each site where the people live who obtain their goods or services from that site. (In computational geometry the sites are traditionally viewed as post offices where customers want to post their letters-hence the subtitle of this chapter.) To study this question we make the following simplifying assumptions:

the price of a particular good or service is the same at every site;

the cost of acquiring the good or service is equal to the price plus the cost of transportation to the site;

the cost of transportation to a site equals the Euclidean distance to the site times a fixed price per unit distance;

consumers try to minimize the cost of acquiring the good or service.

Usually these assumptions are not completely satisfied: goods may be cheaper at some sites than at others, and the transportation cost between two points is probably not linear in the Euclidean distance between them.