@inproceedings{4fd0443bf1d74fcf9f57cc618b835c82,

title = "Certified approximation algorithms for the fermat point and n-ellipses",

abstract = "Given a set A of n points in Rd with weight function w : A → R>0, the Fermat distance function is φ(x):= Pa∈A 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.",

keywords = "Algorithms, Approximation, Certified, Fermat point, N-ellipse, Subdivision",

author = "Kolja Junginger and Ioannis Mantas and Evanthia Papadopoulou and Martin Suderland and Chee Yap",

note = "Funding Information: Funding The work of C. Yap was supported by an USI Visiting Professor Fellowship (Fall 2018); additional support came from NSF Grants # CCF-1564132 and # CCF-2008768. The other authors were partially supported by the SNF project 200021E_154387. Publisher Copyright: {\textcopyright} Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap; licensed under Creative Commons License CC-BY 4.0; 29th Annual European Symposium on Algorithms, ESA 2021 ; Conference date: 06-09-2021 Through 08-09-2021",

year = "2021",

month = sep,

day = "1",

doi = "10.4230/LIPIcs.ESA.2021.54",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Petra Mutzel and Rasmus Pagh and Grzegorz Herman",

booktitle = "29th Annual European Symposium on Algorithms, ESA 2021",

}