Volume 50, Number 1, January-March 2016
|Page(s)||157 - 173|
|Published online||12 January 2016|
A geometric perspective of the Weiszfeld algorithm for solving the Fermat−Weber problem
1 COPPE – PESC, Federal University of
Rio de Janeiro, Cidade Universitária, Centro de Tecnologia, Bloco H,
zip 21941-972, Rio de Janeiro − RJ, Brazil.
firstname.lastname@example.org; email@example.com; firstname.lastname@example.org; email@example.com
2 CEFET/RJ − Centro Federal de Educação Tecnológica Celso Suckow da Fonseca, Av. Maracanã, 229, Maracanã, zip 20271-110, Rio de Janeiro − RJ, Brazil.
3 Colégio Pedro II, Campo de São Cristóvão, 177, São Cristóvão, zip 20921-903, Rio de Janeiro − RJ, Brazil.
Accepted: 12 June 2015
The Fermat−Weber problem is a classical location problem that has the Weiszfeld algorithm as its main iterative solution method. This article presents a geometric interpretation of its local convergence for the particular case of three points, with the solution constrained to be an interior point, which is fundamental to the present geometric interpretation. This constraint, on the other hand, implies that the weights associated to each point must obey triangle inequalities. The eigenvalues analysis is developed considering that all weights have the same value, which simplifies calculation and explanation, but the generalization of this analysis is straightforward, as commented in the text. Step-size scaling is also considered for accelerating the convergence rate. The accompanying eigenvalues analysis determines step-size multiplier ranges that ensure convergence. Moreover, the eigenvalues depend on a parameter that is computed based on the sample points configuration.
Mathematics Subject Classification: 90B85 / 90C90
Key words: Fermat−Weber problem / location problem / Weiszfeld algorithm / local convergence
© EDP Sciences, ROADEF, SMAI 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.