Publication | Closed Access
The Voronoi Partition of a Network and Its Implications in Location Theory
56
Citations
0
References
1992
Year
EngineeringX PNetwork AnalysisEducationComputational ComplexityPolynomial TimeSpatial NetworkPath ProblemsDiscrete MathematicsCombinatorial OptimizationComputational GeometryVoronoi PartitionLocation TheoryCombinatorial ProblemComputer ScienceVoronoi DiagramNetwork TheoryInteger ProgrammingNetwork ScienceGraph TheoryNetwork AlgorithmGeometric Algorithm
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.