From Proximity to Utility: A Voronoi Partition of Pareto Optima

Hsien Chih Chang, Sariel Har-Peled, Benjamin Raichel

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


We present an extension of Voronoi diagrams where not only the distance to the site is taken into account when considering which site the client is going to use, but additional attributes (i.e., prices or weights) are also considered. A cell in this diagram is then the loci of all clients that consider the same set of sites to be relevant. In particular, the precise site a client might use from this candidate set depends on parameters that might change between usages, and the candidate set lists all of the relevant sites. The resulting diagram is significantly more expressive than Voronoi diagrams, but naturally has the drawback that its complexity, even in the plane, might be quite high. Nevertheless, we show that if the attributes of the sites are drawn from the same distribution (note that the locations are fixed), then the expected complexity of the candidate diagram is near linear. To this end, we derive several new technical results, which are of independent interest.

Original languageEnglish (US)
Title of host publication31st International Symposium on Computational Geometry, SoCG 2015
EditorsJanos Pach, Janos Pach, Lars Arge
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages15
ISBN (Electronic)9783939897835
StatePublished - Jun 1 2015
Event31st International Symposium on Computational Geometry, SoCG 2015 - Eindhoven, Netherlands
Duration: Jun 22 2015Jun 25 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other31st International Symposium on Computational Geometry, SoCG 2015


  • Backward analysis
  • Candidate diagram
  • Clarkson-Shor technique
  • Expected complexity
  • Pareto optima
  • Voronoi diagrams

ASJC Scopus subject areas

  • Software

Cite this