Capacity-Constrained Network-Voronoi Diagram

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

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


Given a graph and a set of service center nodes, 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 shortest distances 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 must be contiguous in the graph to simplify communication of allotments. Previous work has focused on honoring either service area contiguity (e.g., Network Voronoi Diagrams) or service center capacity constraints (e.g., min-cost flow), but not both. Our preliminary work introduced a novel Pressure Equalizer (PE) approach for CCNVD to meet the capacity constraints of service centers while maintaining the contiguity of service areas. However, we find that the main bottleneck of the PE algorithm is testing whether service areas are contiguous. In this paper, we extend our previous work and propose novel algorithms that reduce the computational cost. Experiments using road maps from five different regions demonstrate that the proposed approaches significantly reduce computational cost for the PE approach.

Original languageEnglish (US)
Article number7123646
Pages (from-to)2919-2932
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number11
StatePublished - Nov 1 2015

Bibliographical note

Publisher Copyright:
© 1989-2012 IEEE.


  • Capacity Constrained Network Voronoi Diagram
  • Pressure Equalization
  • Service Area Contiguity Checking
  • Spatial Network Partitioning


Dive into the research topics of 'Capacity-Constrained Network-Voronoi Diagram'. Together they form a unique fingerprint.

Cite this