AN OPTIMAL ALGORITHM FOR THE ONLINE CLOSEST-PAIR PROBLEM

被引：16

作者：

SCHWARZ, C ^{[1
]}

SMID, M ^{[1
]}

SNOEYINK, J ^{[1
]}

机构：

[1] UNIV BRITISH COLUMBIA,VANCOUVER V6T 1W5,BC,CANADA

来源：

ALGORITHMICA | 1994年 / 12卷 / 01期

关键词：

COMPUTATIONAL GEOMETRY; CLOSEST PAIR; POINT LOCATION; CENTROID; AMORTIZATION;

D O I：

10.1007/BF01377181

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We give an algorithm that computes the closest pair in a set of n points in k-dimensional space on-line, in 0(n log n) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision of k-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.

引用

页码：18 / 29

页数：12

共 15 条

[1]

Chazelle B., 1982, 23rd Annual Symposium on Foundations of Computer Science, P339, DOI 10.1109/SFCS.1982.58

[2]

DICKERSON MT, 1991, 7TH P ACM S COMP GEO, P234

[3] LINEAR-TIME ALGORITHMS FOR VISIBILITY AND SHORTEST-PATH PROBLEMS INSIDE TRIANGULATED SIMPLE POLYGONS [J].