ISSN:
1572-9125
Schlagwort(e):
F.2.2
;
Computational geometry
;
plane-sweep algorithm
;
proximity problems
;
all-nearest-neighbor problem
;
probabilistic analysis of algorithms
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
Abstract A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in thek-dimensional Euclidean spaceE k ,k〉1, projects the given point setS onto thex-axis. For each pointq εS a nearest neighbor inS under anyL p -metric (1 ≤p ≤ ∞) is found by sweeping fromq into two opposite directions along thex-axis. If δ q denotes the distance betweenq and its nearest neighbor inS the sweep process stops after all points in a vertical 2δ q -slice centered aroundq have been examined. We show that this algorithm solves the all-nearest-neighbors problem forn independent and uniformly distributed points in the unit cube [0,1] k in Θ(n 2−1/k ) expected time, while its worst-case performance is Θ(n 2).
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01933171
Permalink