Hitting Buneman Circles

We discuss Peter Buneman’s suggestion that a fibre connection to the internet — a hub — should be available within every circle enclosing a population of at least 2,000 people (a b-circle). This poses the problem of finding a small set, H, of hubs, such that every b-circle contains a hub. We show that a greedy algorithm does not lead to an optimal set of hubs. Instead it models market forces, which are naturally greedy. An unfettered market will exploit the most profitable communities and, just like a greedy algorithm, leave gaps that it is uneconomic to fill. We describe a geometric heuristic for the discovery of efficient hub placements satisfying a purely combinatorial analogue of Buneman’s criterion, and apply it to illustrate the inherent inefficiency of gap-funding in a market-led broadband policy.