Visual Computing

University of Konstanz
2009 Sixth International Symposium on Voronoi Diagrams

Capacity-Constrained Voronoi Diagrams in Continuous Spaces

M. Balzer
Teaser of Capacity-Constrained Voronoi Diagrams in Continuous Spaces


Paper (.pdf, 1.2MB)


A Voronoi diagram of a set of sites partitions a bounded space into regions of different areas. A capacityconstrained Voronoi diagram is a partition in which the area for each Voronoi region is predefined. In this paper, we present two approaches for computing such capacity-constrained Voronoi diagrams in continuous spaces. Our first approach is based on ordinary (non-weighted) distance functions and achieves the capacity constraint by a general optimization of the site locations. Our second approach is based on weighted distance functions and optimizes the weights of the sites. Both approaches are iterative methods that start with an initial set of sites and then optimize the area of one Voronoi region at a time. As a consequence, the dimensionality of the individual optimization problem is minimal, which enables a reliable and fast convergence even for large sets of sites.


  author    = {M. Balzer},
  booktitle = {2009 Sixth International Symposium on Voronoi Diagrams},
  doi       = {10.1109/ISVD.2009.28},
  keywords  = {computational geometry;iterative methods;optimisation;capacity-constrained Voronoi diagram;continuous space;iterative method;weighted distance function;Application software;Computer graphics;Constraint optimization;Convergence;Iterative methods;Optimization methods;Shape;Topology;Visualization},
  month     = {jun},
  pages     = {79--88},
  title     = {Capacity-Constrained Voronoi Diagrams in Continuous Spaces},
  url       = {},
  year      = {2009}