APPROXIMATE CLOSEST-POINT QUERIES IN HIGH DIMENSIONS

被引：41

作者：

BERN, M

机构：

[1] Xerox Corporation, Palo Alto Research Center, Palo Alto

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 45卷 / 02期

关键词：

COMPUTATIONAL GEOMETRY; DATA STRUCTURES; PATTERN MATCHING; CLOSEST-POINT QUERIES; QUADTREES;

D O I：

10.1016/0020-0190(93)90222-U

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given n points in d dimensions, we show how to construct a data structure of space O(d2(d)n) that approximately answers closest-point queries in time O(d2d log n). The returned point is at most O(d1/2) times further from the query point than the true closest point. We also show how to construct a data structure of space O(dn log m), that-with high probability-can answer a sequence of m closest-point queries in time O(d log n log m) per query, with approximation ratio O(d3/2). Our data structures are based on quadtrees.

引用

页码：95 / 99

页数：5

共 8 条

[1] OPTIMAL EXPECTED-TIME ALGORITHMS FOR CLOSEST POINT PROBLEMS [J].

BENTLEY, JL ;

WEIDE, BW ;

YAO, AC .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1980, 6 (04) :563-580

[2]

Dobkin D., 1976, SIAM Journal on Computing, V5, P181, DOI 10.1137/0205015

[3]

Finkel R. A., 1974, Acta Informatica, V4, P1, DOI 10.1007/BF00288933

[4]

Friedman J. H., 1977, ACM Transactions on Mathematical Software, V3, P209, DOI 10.1145/355744.355745

[5]

SAMET H, 1984, ACM COMPUT SURV, V16, P188

[6]

Samet H, 1990, DESIGN ANAL SPATIAL, P191, DOI 10.1007/3-540-52208-5_28

[7] AN O(N LOG N) ALGORITHM FOR THE ALL-NEAREST-NEIGHBORS PROBLEM [J].

VAIDYA, PM .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (02) :101-115

[8]

YAO AC, 1985, 17TH P ANN ACM S THE, P163

← 1 →