Euclidean Minimum Spanning Tree

Let $n,d\in\mathbb{N}$ , and let the input be $n$ points in $\mathbb{R}^d$ . Determine whether their Euclidean minimum spanning tree can be computed in time close to the lower bound $\Omega(n\log n)$ . The source does not specify a more precise target for the phrase ``close to.''

Download

Abstract

The open problem asks whether the Euclidean minimum spanning tree of $n$ points in $\mathbb{R}^d$ can be computed in time close to the $\Omega(n\log n)$ lower bound. The difficulty is most pronounced in large dimension, where the reported upper bounds approach quadratic time.

Background and progress

The origin of the question is uncertain. Let $n\in\mathbb{N}$ denote the number of input points. A lower bound of $\Omega(n\log n)$ is known for the Euclidean minimum spanning tree problem [Grigoriev et al., 1996]. In arbitrary weighted graphs, an optimal minimum spanning tree algorithm is known [Pettie and Ramachandran, 2002]. This does not settle the geometric setting: the Euclidean graph is complete, so time linear in its number of edges is quadratic in $n$ . The reported geometric upper bounds approach quadratic time as the dimension grows [Callahan and Kosaraju, 1995]. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p5.

Reference papers

A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fieldsP. B. Callahan, S. Rao KosarajuJ. Assoc. Comput. Mach. · 1995
A lower bound for randomized algebraic decision treesDima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman SmolenskyProc. 28th Annu. ACM Sympos. Theory Comput. · 1996
An optimal minimum spanning tree algorithmSeth Pettie, Vijaya RamachandranJ. ACM · 2002