The Voronoi Partition of a Network and Its Implications in Location Theory

Given a network N(V, E) and a set of points X_p = {x₁, …, x_p} on N, we first present an algorithm for computing the Voronoi partition of N(V, E) into territories T(x₁), …, T(x_p). After describing two ways to measure the “size” of a territory, we introduce and discuss the more challenging problem of selecting X_p so that the maximum size among the resulting territories is as small as possible. For one especially natural way to measure the size of a territory, we show that this latter problem is NP-complete when p is part of the input, but that the problem can be solved in polynomial time for any fixed p.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.