Document Open Access Logo

Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition)

Authors Ioannis Mantas , Evanthia Papadopoulou , Martin Suderland , Chee Yap

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.69.pdf
  • Filesize: 4.06 MB
  • 6 pages

Document Identifiers

Author Details

Ioannis Mantas
  • Faculty of Informatics, Università della Svizzera italiana (USI), Lugano, Switzerland
Evanthia Papadopoulou
  • Faculty of Informatics, Università della Svizzera italiana (USI), Lugano, Switzerland
Martin Suderland
  • Faculty of Informatics, Università della Svizzera italiana (USI), Lugano, Switzerland
Chee Yap
  • Courant Institute, New York University (NYU), NY, USA

Funding

  • Papadopoulou, Evanthia: supported by the SNF~project~200021E_201356.
  • Suderland, Martin: supported by the SNF~project~200021E_201356.
  • Yap, Chee: supported by NSF Grant No.~CCF-2008768.

Cite AsGet BibTex

Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap. Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 69:1-69:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.69

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Fermat point
  • geometric median
  • Weber point
  • Fermat distance
  • sum of distances
  • n-ellipse
  • multifocal ellipse
  • min-sum Voronoi diagram
  • cluster Voronoi diagram

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, Belén Palop, and Vera Sacristán. The farthest color Voronoi diagram and related problems. In Proceedings of the 17th European Workshop on Computational Geometry (EuroCG 2001), pages 113-116, 2001. Google Scholar
  2. Elena Arseneva and Evanthia Papadopoulou. Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended. Journal of Combinatorial Optimization, 37(2):579-600, 2019. Google Scholar
  3. Franz Aurenhammer and Herbert Edelsbrunner. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern recognition, 17(2):251-257, 1984. Google Scholar
  4. Mihai Badoiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC '02), pages 250-257. ACM, 2002. Google Scholar
  5. Chanderjit Bajaj. The algebraic degree of geometric optimization problems. Discrete & Computational Geometry, 3(2):177-191, 1988. Google Scholar
  6. Gill Barequet, Matthew T Dickerson, and Robert L Scot Drysdale. 2-point site Voronoi diagrams. Discrete Applied Mathematics, 122(1-3):37-54, 2002. Google Scholar
  7. Huck Bennett, Evanthia Papadopoulou, and Chee Yap. Planar minimization diagrams via subdivision with applications to anisotropic Voronoi diagrams. Computer Graphics Forum, 35(5):229-247, 2016. Google Scholar
  8. Prosenjit Bose, Anil Maheshwari, and Pat Morin. Fast approximations for sums of distances, clustering and the Fermat-Weber problem. Computational Geometry, 24(3):135-146, 2003. Google Scholar
  9. Hui Han Chin, Aleksander Madry, Gary L. Miller, and Richard Peng. Runtime guarantees for regression problems. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS '13), pages 269-282. ACM, 2013. Google Scholar
  10. Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC '16), pages 9-21. ACM, 2016. Google Scholar
  11. Herbert Edelsbrunner, Leonidas J Guibas, and Micha Sharir. The upper envelope of piecewise linear functions: algorithms and applications. Discrete & Computational Geometry, 4(1):311-336, 1989. Google Scholar
  12. Sándor P Fekete, Joseph SB Mitchell, and Karin Beurer. On the continuous Fermat-Weber problem. Operations Research, 53(1):61-76, 2005. Google Scholar
  13. Sariel Har-Peled and Akash Kushal. Smaller coresets for k-median and k-means clustering. Discrete & Computational Geometry, 37(1):3-19, 2007. Google Scholar
  14. Daniel P Huttenlocher, Klara Kedem, and Micha Sharir. The upper envelope of Voronoi surfaces and its applications. Discrete & Computational Geometry, 9(3):267-291, 1993. Google Scholar
  15. Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland, and Chee Yap. Certified approximation algorithms for the Fermat point and n-ellipses. In Proceedings of the 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  16. Long Lin and Chee Yap. Adaptive isotopic approximation of nonsingular curves: the parameterizability and nonlocal isotopy approach. Discrete & Computational Geometry, 45(4):760-795, 2011. Google Scholar
  17. Ioannis Mantas, Evanthia Papadopoulou, Vera Sacristán, and Rodrigo I Silveira. Farthest color Voronoi diagrams: Complexity and algorithms. In Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN 2020), pages 283-295. Springer, 2021. Google Scholar
  18. Gyula Sz Nagy. Tschirnhaus’sche Eiflächen und Eikurven. Acta Mathematica Academiae Scientiarum Hungarica, 1(1):36-45, 1950. Google Scholar
  19. Jiawang Nie, Pablo A. Parrilo, and Bernd Sturmfels. Semidefinite representation of the k-ellipse. In Algorithms in algebraic geometry, pages 117-132. Springer, 2008. Google Scholar
  20. Evanthia Papadopoulou and Der-Tsai Lee. The Hausdorff Voronoi diagram of polygonal objects: A divide and conquer approach. International Journal of Computational Geometry & Applications, 14(06):421-452, 2004. Google Scholar
  21. Pablo A. Parrilo and Bernd Sturmfels. Minimizing polynomial functions. Algorithmic and quantitative real algebraic geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 60:83-99, 2003. Google Scholar
  22. Simon Plantinga and Gert Vegter. Isotopic approximation of implicit curves and surfaces. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing (SGP), pages 245-254, 2004. Google Scholar
  23. Junpei Sekino. n-ellipses and the minimum distance sum problem. The American mathematical monthly, 106(3):193-202, 1999. Google Scholar
  24. Ehrenfried Walther von Tschirnhaus. Medicina Mentis Et Corporis. Fritsch, Lipsiae, 1695. URL: http://mdz-nbn-resolving.de/urn:nbn:de:bvb:12-bsb10008248-3.
  25. Alfred Weber. Über den Standort der Industrien. Tübingen: Verlag von JCB Mohr, 1909. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact