Fast approximations for sums of distances, clustering and the Fermat-Weber problem

被引:48
作者
Bose, P [1 ]
Maheshwari, A [1 ]
Morin, P [1 ]
机构
[1] Carleton Univ, Sch Comp Sci, Ottawa, ON K1S 5B6, Canada
来源
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2003年 / 24卷 / 03期
基金
加拿大自然科学与工程研究理事会;
关键词
Fermat-Weber center; range tree; quadtree; clustering; facility location; data structure; randomization;
D O I
10.1016/S0925-7721(02)00102-5
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We describe two data structures that preprocess a set S of n points in R-d (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within a factor of epsilon. This preprocessing technique has several applications in clustering and facility location. Using it, we derive an O(n log n) time deterministic and O(n) time randomized epsilon-approximation algorithm for the so called Fermat-Weber problem in any fixed dimension. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:135 / 146
页数:12
相关论文
共 21 条
[1]  
[Anonymous], 1991, P 3 CANADIAN C COMPU
[2]   THE ALGEBRAIC DEGREE OF GEOMETRIC OPTIMIZATION PROBLEMS [J].
BAJAJ, C .
DISCRETE & COMPUTATIONAL GEOMETRY, 1988, 3 (02) :177-191
[3]  
BESPAMYATNIKH S, 1999, P 6 INT WORKSH ALG D, P318
[4]  
Brimberg J., 1995, Location Science, V3, P203, DOI 10.1016/0966-8349(95)00015-1
[5]   ALGEBRAIC OPTIMIZATION - THE FERMAT-WEBER LOCATION PROBLEM [J].
CHANDRASEKARAN, R ;
TAMIR, A .
MATHEMATICAL PROGRAMMING, 1990, 46 (02) :219-224
[6]  
Church R. L., 1978, Transportation Science, V12, P107, DOI 10.1287/trsc.12.2.107
[7]  
ELGINDY H, 1982, ORSA J COMPUT, V4, P418
[8]   Robust distance-based clustering with applications to spatial data mining [J].
Estivill-Castro, V ;
Houle, ME .
ALGORITHMICA, 2001, 30 (02) :216-242
[9]  
Francis RL., 1974, FACILITY LAYOUT LOCA
[10]  
Indyk P., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P428, DOI 10.1145/301250.301366