Shinichi Honiden, Michael E. Houle, and Christian Sommer

ISVD 2009 - 6th International Symposium on Voronoi Diagrams in Science and Engineering

Many facility location problems are concerned with minimizing operation and transportation costs by partitioning territory into regions of similar size, each of which is served by a facility. For many optimization problems, the overall cost can be reduced by means of a partitioning into balanced subsets, especially in those cases where the cost associated with a subset is superlinear in its size. In this paper, we consider the problem of generating a Voronoi partition of a discrete graph so as to achieve balance conditions on the region sizes. Through experimentation, we first establish that the region sizes of randomly-generated graph Voronoi diagrams vary greatly in practice. We then show how to achieve a balanced partition of a graph via Voronoi site resampling. For bounded-degree graphs, where each of the *n* nodes has degree at most *d*, and for an initial randomly-chosen set of *s* Voronoi nodes, we prove that, by extending the set of Voronoi nodes using an algorithm by Thorup and Zwick, each Voronoi region has size at most *4dn/s + 1* nodes, and that the expected size of the extended set of Voronoi nodes is at most *2s* log *n*.

@inproceedings{HHS09, author = {Shinichi Honiden and Michael E. Houle and Christian Sommer}, title = {Balancing Graph Voronoi Diagrams}, booktitle = {6th International Symposium on Voronoi Diagrams (ISVD)}, year = {2009}, pages = {183--191}, url = {http://dx.doi.org/10.1109/ISVD.2009.26}, doi = {10.1109/ISVD.2009.26}, }

Official version

Local version (203.2 KB)

See also Approximate Shortest Path Queries in Graphs Using Voronoi Duals.

Home → Publications → Balancing Graph Voronoi Diagrams