On the Fermat-Weber center of a convex object

被引：15

作者：

Carmi, P

Har-Peled, S

Katz, MJ ^{[1
]}

机构：

[1] Ben Gurion Univ Negev, Dept Comp Sci, IL-84105 Beer Sheva, Israel

[2] Univ Illinois, Dept Comp Sci, Urbana, IL 61801 USA

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2005年 / 32卷 / 03期

基金：

美国国家科学基金会;

关键词：

Fermat-Weber center; approximation algorithms;

D O I：

10.1016/j.comgeo.2005.01.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show that for any convex object Q in the plane, the average distance from the Fermat-Weber center of Q to the points in Q is at least Delta(Q)/7, where A(Q) is the diameter of Q, and that there exists a convex object P for which this distance is Delta(P)/6. We use this result to obtain a linear-time approximation scheme for finding an approximate Fermat-Weber center of a convex polygon Q. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：188 / 195

页数：8

共 5 条

[1] THE ALGEBRAIC DEGREE OF GEOMETRIC OPTIMIZATION PROBLEMS [J].