2026-08-14T10:02:45Z https://drops.dagstuhl.de/oai

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

Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition) Mantas, Ioannis Papadopoulou, Evanthia Suderland, Martin Yap, Chee Fermat point geometric median Weber point Fermat distance sum of distances n-ellipse multifocal ellipse min-sum Voronoi diagram cluster Voronoi diagram Given a set P of n points, the sum of distances function of a point x is d_{P}(x) : = ∑_{p ∈ P} ||x - p||. Using a subdivision approach with soft predicates we implement and visualize approximate solutions for three different problems involving the sum of distances function in ℝ². Namely, (1) finding the Fermat-Weber point, (2) constructing n-ellipses of a given set of points, and (3) constructing the nearest Voronoi diagram under the sum of distances function, given a set of point clusters as sites. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ioannis Mantas and Evanthia Papadopoulou and Martin Suderland and Chee Yap 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.69 urn:nbn:de:0030-drops-160773 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.69 eng https://creativecommons.org/licenses/by/4.0/legalcode