ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

An optimal algorithm for the on-line closest-pair problem (1994)

Schwarz, C. ; Smid, M. ; Snoeyink, J.

Springer

Algorithmica 12 (1994), S. 18-29

add to mindlist on the mindlist

Details

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

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit