Structural properties of voronoi diagrams in facility location problems with continuous demand

Igor Averbakh, Oded Berman, Jörg Kalcsics, Dmitry Krass

Research output: Contribution to journalArticlepeer-review

Abstract

We consider facility location problems where the demand is continuously and uniformly distributed over a convex polygon with m vertices in the rectilinear plane, n facilities are already present, and the goal is to find an optimal location for an additional facility. Based on an analysis of structural properties of incremental Voronoi diagrams, we develop polynomial exact algorithms for five conditional location problems. The developed methodology is applicable to a variety of other facility location problems with continuous demand. Moreover, we briefly discuss the Euclidean case.

Original languageEnglish
Pages (from-to)394-411
Number of pages18
JournalOperations Research
Volume63
Issue number2
Early online date2 Mar 2015
DOIs
Publication statusPublished - Mar 2015

Keywords

  • Continuous facilities location
  • Covering problem
  • Market share problem
  • Median problem
  • Voronoi diagrams

Fingerprint

Dive into the research topics of 'Structural properties of voronoi diagrams in facility location problems with continuous demand'. Together they form a unique fingerprint.

Cite this