ISSN:
1432-0541
Schlagwort(e):
Computational geometry
;
Closest pair
;
Point location
;
Centroid
;
Amortization
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01377181
Permalink