Balancing Graph Voronoi Diagrams

Shinichi Honiden, Michael E. Houle, and Christian Sommer
ISVD 2009 - 6th International Symposium on Voronoi Diagrams in Science and Engineering (pp. 183-191)

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)

Home → Publications → Balancing Graph Voronoi Diagrams