Back to Search
Start Over
MINIMAL LENGTH TREE NETWORKS ON THE UNIT SPHERE.
- Source :
- Annals of Operations Research; 1991, Vol. 33 Issue 1-4, p503-535, 33p, 25 Diagrams, 1 Chart
- Publication Year :
- 1991
-
Abstract
- This paper considers the problem of finding minimal length tree networks on the unit sphere Φ of a given point set (V) where distance is measured along great circular arcs. The related problems of finding a Steiner Minimal Tree SMT (V) and of finding a Minimum Spanning Tree MST(V) are treated through a simplicial decomposition technique based on computing the Delaunay Triangulation DT (V) and the Voronoi Diagram VD(V) of the given point set. O (N log N) algorithms for computing DT(V), VD(V), and WST(V) as well as an O(N log N) heuristic for finding a sub-optimal SMT(V) solution are presented, together with experimental results for randomly distributed points on Φ. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02545330
- Volume :
- 33
- Issue :
- 1-4
- Database :
- Complementary Index
- Journal :
- Annals of Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 18650968