An O(N log N) minimal spanning tree algorithm for N points in the plane (Q1082081)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An O(N log N) minimal spanning tree algorithm for N points in the plane |
scientific article; zbMATH DE number 3972204
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An O(N log N) minimal spanning tree algorithm for N points in the plane |
scientific article; zbMATH DE number 3972204 |
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
