ISSN:
1432-0541
Keywords:
Computational geometry
;
Closest pair
;
Point location
;
Centroid
;
Amortization
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We give an algorithm that computes the closest pair in a set ofn points ink-dimensional space on-line, inO(n logn) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision ofk-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01377181