Computing euclidean maximum spanning trees |
| |
Authors: | Clyde Monma Michael Paterson Subhash Suri Frances Yao |
| |
Affiliation: | 1. Bell Communications Research, Morristown, USA 2. University of Warwick, Coventry, England 3. Xerox PARC, Palo Alto, USA
|
| |
Abstract: | An algorithm is presented for finding a maximum-weight spanning tree of a set ofn points in the Euclidean plane, where the weight of an edge (p i ,p j ) equals the Euclidean distance between the pointsp i andp j . The algorithm runs inO(n logh) time and requiresO(n) space;h denotes the number of points on the convex hull of the given set. If the points are vertices of a convex polygon (given in order along the boundary), then our algorithm requires only a linear amount of time and space. These bounds are the best possible in the algebraic computation-tree model. We also establish various properties of maximum spanning trees that can be exploited to solve other geometric problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|