2026-07-23T18:05:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14635 2024-03-12T12:00:09Z ddc:004 open_access

Certified Approximation Algorithms for the Fermat Point and n-Ellipses Junginger, Kolja Mantas, Ioannis Papadopoulou, Evanthia Suderland, Martin Yap, Chee Fermat point n-ellipse subdivision approximation certified algorithms 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*‖<ε. 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 x̃*, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kolja Junginger and Ioannis Mantas and Evanthia Papadopoulou and Martin Suderland and Chee Yap 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.54 urn:nbn:de:0030-drops-146359 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.54 eng https://creativecommons.org/licenses/by/4.0/legalcode