An O(N log N) minimal spanning tree algorithm for N points in the plane (Q1082081)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An O(N log N) minimal spanning tree algorithm for N points in the plane |
scientific article |
Statements
An O(N log N) minimal spanning tree algorithm for N points in the plane (English)
0 references
1986
0 references
We present a divide-and-conquer algorithm to construct minimal spanning trees out of a set of points in two dimensions. This algorithm is based upon the concept of Voronoi diagrams. If implemented in parallel, its time complexity is O(N) and it requires O(log N) processors where N is the number of input points.
0 references
parallel implementation
0 references
divide-and-conquer algorithm
0 references
Voronoi diagrams
0 references
time complexity
0 references
