Certified approximation algorithms for the fermat point and n-ellipses

Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, Chee Yap

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


Given a set A of n points in Rd with weight function w : A → R>0, the Fermat distance function is φ(x):= PaA w(a)∥x−a∥. A classic problem in facility location dating back to 1643, is to find the Fermat point x, the point that minimizes the function φ. We consider the problem of computing a point xe that is an ε-approximation of x in the sense that ∥xe − x∥ < ε. The algorithmic literature has so far used a different notion based on ε-approximation of the value φ(x). We devise a certified subdivision algorithm for computing xe, enhanced by Newton operator techniques. We also revisit the classic Weiszfeld-Kuhn iteration scheme for x, turning it into an ε-approximate Fermat point algorithm. Our second problem is the certified construction of ε-isotopic approximations of n-ellipses. These are the level sets φ1(r) for r > φ(x) and d = 2. Finally, all our planar (d = 2) algorithms are implemented in order to experimentally evaluate them, using both synthetic as well as real world datasets. These experiments show the practicality of our techniques.

Original languageEnglish (US)
Title of host publication29th Annual European Symposium on Algorithms, ESA 2021
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772044
StatePublished - Sep 1 2021
Event29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal
Duration: Sep 6 2021Sep 8 2021

Publication series

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


Conference29th Annual European Symposium on Algorithms, ESA 2021
CityVitual, Lisbon


  • Algorithms
  • Approximation
  • Certified
  • Fermat point
  • N-ellipse
  • Subdivision

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Certified approximation algorithms for the fermat point and n-ellipses'. Together they form a unique fingerprint.

Cite this