An O(N log N) minimal spanning tree algorithm for N points in the plane (Q1082081): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
| Property / author | |||
| Property / author: Ruei-Chuan Chang / rank | |||
| Property / author | |||
| Property / author: Richard Chia-Tung Lee / rank | |||
Revision as of 11:34, 20 February 2024
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
