Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428768 | Information Processing Letters | 2008 | 4 Pages |
Abstract
Given a point set in a fixed dimension, we note that a well-separated pair decomposition can be found in linear time if we assume that the ratio of the farthest pair distance to the closest pair distance is polynomially bounded. Many consequences follow; for example, we can construct spanners or solve the all-nearest-neighbors problem in linear time (under the same assumption), and we compute an approximate Euclidean minimum spanning tree in linear time (without any assumption).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics