The Voronoi Partition of a Network and Its Implications in Location Theory
S. Louis Hakimi, Martine Labbé Labbé, Edward Schmeichel
ORSA Journal on Computing · 1992 · Volume 4 · Issue 4
Abstract
Given a network N ( V , E ) and a set of points X p = { x 1 , …, x p } on N , we first present an algorithm for computing the Voronoi partition of N ( V , E ) into territories T ( x 1 ), …, 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.
Keywords
networks/graphs
Enable JavaScript for citation tools and additional paper interactions.