@inproceedings{a8e06c2d310c4846838be0354b37b4b1,
title = "Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram",
abstract = "Given a set P of n points, the sum of distances function of a point x is dPpxq:“rpPP ||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 R2. 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.",
keywords = "Fermat distance, Fermat point, Weber point, cluster Voronoi diagram, geometric median, min-sum Voronoi diagram, multifocal ellipse, n-ellipse, sum of distances",
author = "Ioannis Mantas and Evanthia Papadopoulou and Martin Suderland and Chee Yap",
note = "Funding Information: Funding Evanthia Papadopoulou: supported by the SNF project 200021E_201356. Martin Suderland: supported by the SNF project 200021E_201356. Chee Yap: supported by NSF Grant No. CCF-2008768. Publisher Copyright: {\textcopyright} Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap; licensed under Creative Commons License CC-BY 4.0; 38th International Symposium on Computational Geometry, SoCG 2022 ; Conference date: 07-06-2022 Through 10-06-2022",
year = "2022",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SoCG.2022.69",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Xavier Goaoc and Michael Kerber",
booktitle = "38th International Symposium on Computational Geometry, SoCG 2022",
}