Certified Approximation Algorithms for the Fermat Point and n-Ellipses
Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, Chee Keng Yap · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2021
Given a set A of n points in ℝ^d with weight function w: A→ℝ_{> 0}, the Fermat distance function is φ(x): = ∑_{a∈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 x̃* that is an ε-approximation of x* in the sense that ‖x̃*-x*‖ φ(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.