Capacity-constrained network-Voronoi diagram: A summary of results

Kwang Soo Yang, Apurv Hirsh Shekhar, Dev Oliver, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations


Given a graph and a set of service centers, a Capacity Constrained Network-Voronoi Diagram (CCNVD) partitions the graph into a set of contiguous service areas that meet service center capacities and minimize the sum of the distances (min-sum) from graph-nodes to allotted service centers. The CCNVD problem is important for critical societal applications such as assigning evacuees to shelters and assigning patients to hospitals. This problem is NP-hard; it is computationally challenging because of the large size of the transportation network and the constraint that Service Areas (SAs) must be contiguous in the graph to simplify communication of allotments. Previous work has focused on honoring either service center capacity constraints (e.g., min-cost flow) or service area contiguity (e.g., Network Voronoi Diagrams), but not both. We propose a novel Pressure Equalizer (PE) approach for CCNVD to meet the capacity constraints of service centers while maintaining the contiguity of service areas. Experiments and a case study using post-hurricane Sandy scenarios demonstrate that the proposed algorithm has comparable solution quality to min-cost flow in terms of min-sum; furthermore it creates contiguous service areas, and significantly reduces computational cost.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings
Number of pages18
StatePublished - Aug 13 2013
Event13th International Symposium on Spatial and Temporal Databases, SSTD 2013 - Munich, Germany
Duration: Aug 21 2013Aug 23 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8098 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th International Symposium on Spatial and Temporal Databases, SSTD 2013


  • Capacity Constrained Network Voronoi Diagram
  • Pressure Equalization
  • Spatial Network Partitioning


Dive into the research topics of 'Capacity-constrained network-Voronoi diagram: A summary of results'. Together they form a unique fingerprint.

Cite this