On the Fermat-Weber Point of a Polygonal Chain and its Generalizations

• Autorzy: Bhattacharya Bhargab.B.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we study the properties of the Fermat-Weber point for a set of fixed points, whose arrangement coincides with the vertices of a regular polygonal chain. A k-chain of a regular n-gon is the segment of the boundary of the regular n-gon formed by a set of k (≤n) consecutive vertices of the regular n-gon. We show that for every odd positive integer k, there exists an integer N(k), such that the Fermat-Weber point of a set of k fixed points lying on the vertices a k-chain of a n-gon coincides with a vertex of the chain whenever n≥ N(k). We also show that πm(m + 1) - .π^2/4. . N(k)≤πm(m + 1) + 1., where k (= 2m + 1) is any odd positive integer. We then extend this result to a more general family of point set, and give an O(hk log k) time algorithm for determining whether a given set of k points, having h points on the convex hull, belongs to such a family.

Słowa kluczowe

EN

computational geometry; facility location; Fermat-Weber problem; optimization; polygons

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 4
• Strony: 331--343
• Opis fizyczny: Bibliogr. 23 poz., tab., wykr.

Twórcy

autor

Bhattacharya Bhargab.B.

• Indian Statistical Institute 203 B. T. Road, Kolkata, India,

Bibliografia

• [1] L. Anderegg, M. Cieliebak, G. Prencipe, Efficient Algorithms for Detecting Regular Point Configurations; Lecture Notes in Computer Science, Vol. 3701, 23-35, 2005.
• [2] C. Bajaj, The Algebraic Degree of Geometric Optimization Problems; Discrete and Computational Geometry, Vol. 3, 177-191, 1988.
• [3] P. Bose, A. Maheshwari, P. Morin, Fast Approximations for Sums of Distances, Clustering and the Fermat-Weber Problem; Computational Geometry: Theory and Applications, Vol. 24, 135-146, 2003.
• [4] R. E. Burkard,M. Galavii, E. Gassner, The inverse Fermat-Weber problem; European Journal of Operations Research, Vol. 206, 11-17, 2010.
• [5] T. M. Chan, Output-sensitive results on convex hulls, extreme points, and related problems; Discrete and Computational Geometry, Vol. 16, 369-387, 1996.
• [6] P. Chaudhuri, On a Geometric Notion of Quantiles for Multivariate Data; Journal of the American Statistical Association, Vol. 91, 862-872, 1996.
• [7] E. Cockayne, Z. Melzak, Euclidean Constructibility in Graph-Minimization Problems; Math. Magazine, Vol. 42, 206-208, 1969.
• [8] Z. Drezner, K. Klamroth, A. Schöbel, G. O.Wesolowsky, TheWeber Problem, in Z. Drezner, H.W. Hamacher (Eds.), Facility Location: Applications and Theory; Springer, 2002.
• [9] G. Fagnano, Problemata quaedam ad methodum maximorum et minimorum spectantia; Nova Acta Eruditorum, 281-303, 1775 (Mensis Iunii, published in 1779).
• [10] C. Gini, L. Galvani, Di talune estensioni dei concetti di media a caratteri qualitivi; Metron, Vol. 8, 3-209, 1929. (Partial English Translation in Journal of the American Statistical Association, Vol. 25, 448-450.)
• [11] J. B. S. Haldane, Note on the Median of a Multivariate Distribution; Biometrika, Vol. 35, 414-415, 1948.
• [12] G. Jalal, J. Krarup, Geometrical Solution to the Fermat Problemwith ArbitraryWeights; Annals ofOperations Research, Vol. 123, 67-104, 2003.
• [13] D. G. Kirkpatrick, R. Seidel, The utimate planar convex hull algorithm?; SIAM Journal on Computing, Vol. 15, 287-299, 1986.
• [14] J. Krarup, S. Vajda, On Torricelli's Geometrical Solution to a Problem of Fermat; IMA Journal of Mathematics Applied in Business and Industry, Vol. 8, 215-224, 1997.
• [15] Y. S. Kupitz, H. Martini, Geometric Aspects of the Generalized Fermat-Weber Problem; Intuitive Geometry, Bolyai Soceity, Mathematical Studies Vol. 6, 55-127, 1997.
• [16] S. L. Loney, Plane Trigonometry, Part I; Cambridge University Press, London, 1966.
• [17] F. Plastria, Four Point Fermat Location Problems Revisited: New Proofs and Extensions of Old Results; IMA Journal of Management Mathematics, Vol. 17, 387-396, 2006.
• [18] E. Torricelli (c. 1640), De maximis et minimis; Opere di Evangelista Torricelli, G. Loria and G. Vassura (Eds.), Faenza, Italy, 1919.
• [19] Y. Vardi, C.H. Zhang, A Modified Weiszfeld Algorithm for the Fermat-Weber Location Problem; Math. Program., Ser. A, Vol. 90, 559-566, 2001.
• [20] A. Weber, Uber Den Standord Der Industrien, Tubigen, 1909. (English Translation by C. J. Freidrich, Alfred Weber's Theory of Location of Industries; Chicago University Press, 1929.)
• [21] E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnes est minimum; Tohoku Mathematics Journal, Vol. 43, 355-386, 1937. (Translated and annotated by F. Plastria, On the point for which the sum of distances to n given points is minimum; Annals of Operations Research, Vol. 167 (1), 7-41, 2009.)
• [22] G. Wesolowsky, The Weber problem: History and Perspective; Location Science, Vol. 1, 5-23, 1993.
• [23] I.M. Yaglom, Geometric Transformations I; Random House, New York, 1962, (Translated from Russian by Allen Shields).