𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Efficient minimum spanning tree construction without Delaunay triangulation

✍ Scribed by Hai Zhou; Narendra Shenoy; William Nicholls

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
77 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

Given n points in a plane, a minimum spanning tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least (n 2 ) time. More efficient approaches find a minimum spanning tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning tree construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(n log n) sweep-line algorithm to construct a rectilinear minimum spanning tree without using Delaunay triangulation.

πŸ“œ SIMILAR VOLUMES

Efficient distributed algorithm to solve
Efficient distributed algorithm to solve updating minimum spanning tree problem
✍ Jungho Park; Ken'Ichi Hagihara; Nobuki Tokura; Toshimitsu Masuzawa πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 983 KB

## Abstract This paper proposes a distributed algorithm for reconstructing a minimum‐weight spanning tree __T__β€² of a network __N__β€² when link addition and deletion occur in a network __N__ with a minimum‐weight spanning tree __T.__ In this algorithm each processor uses information whose adjacent l

Improving the efficiency of parallel min
Improving the efficiency of parallel minimum spanning tree algorithms
✍ Ka Wong Chong; Yijie Han; Yoshihide Igarashi; Tak Wah Lam πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 203 KB

This paper presents results which improve the e ciency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(log n) time with O((m+n) log n) operations. Our CRCW PRAM algorithm runs in O(log n) time with O((m