Cloudonomics: The Business Value of Cloud Computing, + Website

Circle Covering and Circle Packing

To further abstract the problem, we consider what happens as we adjust the radius, r, of a circle about a given service node or multiple service nodes. This is a way of viewing the problem of finding a nearby “node,” such as a hamburger joint, coffee shop, or mobile base station: If you want to find one less than a mile away, say, you must be situated within the circular area swept by a radius of one mile about the node. It turns out that for a circle with worst-case distance r, the expected value of the distance to the center of a point selected at random within the circle is ⅔;r. This means that when we talk about distance on a plane, we needn’t exactly specify worst-case versus expected, as they are the same except for a scaling constant.

Coverage impacts more than just latency. Placing cell sites—or related technologies such as picocells, femtocells, wireless access points, or distributed antenna systems—is more about ensuring reception than addressing latency. Moreover, sometimes we prefer less coverage rather than more. Since the capacity of cellular base stations and wireless access points is constrained, more users can be served by more sites each covering less area. The general abstract coverage problem—determining whether k sites can cover an arbitrary set of points on a plane—is computationally intractable.3 In the real world it is somewhat easier: Service providers prioritize the most relevant countries economically, then the most ...