TREE-WEIGHTED NEIGHBORS AND GEOMETRIC k SMALLEST SPANNING TREES
- 1 June 1994
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 04 (02) , 229-238
- https://doi.org/10.1142/s0218195994000136
Abstract
We compute the k smallest spanning trees of a point set in the planar Euclidean metric in time O(n log n log k + k min (k, n)1/2 log (k/n)), and in the rectilinear metric in time O(n log n + n log log n log k + k ( min {k, n})1/2 log (k/n)). In three or four dimensions our time bound is O(n4/3 + ∊ + k( min {k, n})1/2 log (k/n)), and in higher dimensions the bound is O(n2−2/(⌈d/2⌉+1)+∊ + kn1/2 log n). Our technique involves a method of computing nearest neighbors using a modified set of distances formed by subtracting tree path lengths from the Euclidean distance.Keywords
This publication has 0 references indexed in Scilit: