Dynamic Euclidean minimum spanning trees and extrema of binary functions |
| |
Authors: | D Eppstein |
| |
Institution: | (1) Department of Information and Computer Science, University of California, 92717 Irvine, CA, USA |
| |
Abstract: | We maintain the minimum spanning tree of a point set in the plane subject to point insertions and deletions, in amortized
timeO(n
1/2 log2
n) per update operation. We reduce the problem to maintaining bichromatic closest pairs, which we solve in timeO(n
e
) per update. Our algorithm uses a novel construction, theordered nearest neighbor path of a set of points. Our results generalize to higher dimensions, and to fully dynamic algorithms for maintaining minima of
binary functions, including the diameter of a point set and the bichromatic farthest pair.
This research was supported in part by NSF Grant CCR-9258355 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|