AN OPTIMAL ALGORITHM FOR THE ONLINE CLOSEST-PAIR PROBLEM

Authors
SCHWARZ C SMID M SNOEYINK J
Citation
C. Schwarz et al., AN OPTIMAL ALGORITHM FOR THE ONLINE CLOSEST-PAIR PROBLEM, Algorithmica, 12(1), 1994, pp. 18-29
Citations number
15
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
12
Issue
1
Year of publication
1994
Pages
18 - 29
Database
ISI
SICI code
0178-4617(1994)12:1<18:AOAFTO>2.0.ZU;2-K
Abstract
We give an algorithm that computes the closest pair in a set of n poin ts in k-dimensional space on-line, in 0(n log n) time. The algorithm o nly 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 ba lanced decomposition of this tree.